# Theory of Computation-計算理論
:::success
:::spoiler 目錄
[TOC]
:::
## Mathematical Preliminaries and Notation
:::info
- Sets: $S$
Universal Set ,or universe of discourse : $U$ all possible element
- union: $\cup$
intersection: $\cap$
difference: $-$
- complement:
1. $\overline{\text{even integers}}=\text{odd integers}$
2. $\overline{\varnothing}=\text{Universal Set}$
- Demorgan's Law
- Empty,Null Set: $\varnothing$
- Disjoint: $A\cap B = \varnothing$
- $\lvert{A}\rvert$ (set size ,or cardinality)
:::
:::warning
- Subset: $\subseteq\text{or}\supseteq$
Proper Set: $\subset\text{or}\supset$
- 如果集合$A$ 所有的元素，集合$B$ 也都同時包含，則可計成 $\text{A}\subseteq\text{B}$
若同時$A\neq B$ 則可計成 $\text{A}\subset\text{B}$
- $\varnothing$是所有集合的子集合，
也是所有集合的真子集。
- Powerset: $\mathcal{P}{(S)}\text{或做}2^S$
- The set of all the subset(該集合全部子集為元素構成的集合)
- Example:
- $\text{S = {a,b,c}}$
- $2^S = \{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$
- [$2^S$的記法](https://reurl.cc/XmWeMa)
- 卡氏積Cartesian(笛卡爾) Product ( $A \times B$ )
- 舉個例子:撲克牌花色與數字。組成的撲克牌。
$\text{花色}=\{\text{H,D,C,S}\}$ 4種
$\text{數字}=\{\text{A,2,3,4,5,6,7,8,9,10,J,Q,K}\}$ 13種
- 牌數 $4\times 13=52$ 種
- Note that the **order** in which the elements of a pair are written matters:
花色$\times$數字 is the pair (梅花,3), but (3,梅花) is not
- Cartesian product 可以擴充超過兩個集合( $A_1 \times A_2 \times ... \times A_n$ )
- Partition
1. The subset $S_1, S_2, …,S_n$ are mutually disjoint;
2. $S_1 \cup S_2 \cup …\cup S_n = S$;
3. None of the $S_i$ is empty.
- Then $S_1, S_2, …, S_n$ is called a **partition** of $S$.
:::
:::danger
- 易混淆
- $\subseteq$ 子集(包含等於集合)
- $\subset$ 真子集(不等於集合)
- a element $\in$ a set
:::
### Asymptotic Analysis
$O$ (Big-O): Upper Bounding Function
$\Omega$ (Big-Omega): Lower Bounding Function
$\Theta$ (Big-Theta): Tightly Bounding Function 夾擠
:::success
- $f(n)= O(g(n))$ 義為：$g(n)$是$f(n)$的上界
白話一點就是 $f(n)$ 的次方數必須 $\leq g(n)$
- 同理：
- $f(n)= \Omega (g(n))$ 就是 $f(n)$ 的次方數必須 $\geq g(n)$
- $f(n)= \Theta (g(n))$ 就是 $f(n)$ 的次方數必須 $= g(n)$
:::
### Relations
- Relations are more general than functions
- if $x = y \text{ 可說是 } x \equiv y$
- if $x \equiv y {\color{red}{\text{ 不可說 }}} x = y$
- Reflexive(反身性)
- $\text{x R x}$
- Symmetric(對稱性)
- $\text{x R y}\Rightarrow \text{y R x}$
- Transitive(遞移性)
- $\text{x R y and y R z} \Rightarrow\text{x R z}$
- Equivalence Relation $(\equiv)$
- 等效的
### GRAPHS(圖)
一些圖的類型，即表示方式。
- digraph (directed graph) 有(方)向圖
- Euler Tour
一個包含所有邊的循環
- Hamiltonian Cycle
包含所有點的簡單循環
### Proof Techniques(證明方法)
- 直接證明(Direct/Constructive Proof)
- 歸納法(Proof by Induction)
- 反證法(Proof by Contradiction)
## Three Basic Concepts
:::success
- Languages
- Grammars
- Automata
:::
- A languages is a **set** of **strings**
- A language is any subset of $\Sigma^*$
- 基本符號
$\Sigma=\text{{可能出現的字母}}$ 通常為Alphabet(字母)，也可自己定義
- String Operations
:::info
- $wv$ concatenation 串接
- $w^R$ reverse 倒轉
- $\lvert w\rvert = n$ Lenght
- $\color{red}{\lambda}$ 長度為 0 的string，非空集合。
- $w^0=\lambda$
- Substring 子字串
- Prefix and Suffix
- $w=uv$
- $u$ ：prefix
- $v$ ：suffix
- 任意 $w$ 可以由 prefix and suffix 組成
- prefix and suffix 可以為 $\lambda$
- Example：$w=abbab$
- | Prefixes | Suffixes |
| --------- | --------- |
| $\lambda$ | abbab |
| a | bbab |
| ab | bab |
| abb | ab |
| abba | b |
| abbab | $\lambda$ |
- A nonempty string $y$ is a **proper** prefix, suffix, sub-string of $x$
if it is a prefix, suffix, sub-string of $x$ and $x\neq y$
- Another Operation...
$w^n = ww...w$ 有$n$個
$\Sigma^*$: 從 $\Sigma$ 中，任意取任意數量的集合，包含$\lambda$，是無窮的集合。
$\Sigma^+$: 不包含$\lambda$ ，其餘與上者相同，意為 $\Sigma^* - \lambda$
:::
- finite set
可全部列出
- infinite set
- 找到描述句去描述
- 集合元素是無窮的，但仍有不可達成的元素
:::danger
- Sets: $\varnothing =\{\} \neq \{\lambda\}$
- Set size: $|\varnothing| =|\{\}| =0$
- Set size: $|\{\lambda\}|=1$
- String length: $|\lambda|=0$
:::
- ==**Operations on Languages**==
- Reverse $L^R$
- Concatenation $L_1L_2$
- Star-Closure $L^*$
- Positive Closure $L^+$
- Grammars
- 找工具去看懂 language (人看得懂)
- Definition: G(a grammar)可以被4個部分定義
$\text{G=(V, T, S, P)}$
- $V$ 變數
- $T$ terminal
- $S$ start
- $P$ 過程
- ==Language 可以是無窮集，但其表現形式有其極限。==
## Automata
一個數位電腦的一個抽象模型，
Automatom = CUP + Program memory
:::success
- Deterministic
- Nondeterministic
- Accepter output YES or NO
- Transducer output strings of symbols
:::
### DFA(Deterministic Finite Accepters)
- 有限狀態機(FSM)的數學模型，根據當前狀態判斷下一個狀態為何。
- $M=(Q,\Sigma,\delta,q_0,F)$
- DFA中最重要的 $\delta$ function (Transition Function)，表示DFA怎麼跑。可以用表或是圖呈現。
- $\delta^*$ 一次性的起點終點和路徑
`//Recursive` 寫法$\delta^*(q_0,input)=q_f$
- $L(M) = \text{{ strings that drive M to a final state}}$
- $L(G)$?
- $L(M)$?
- 要告訴DFA所有的state吃不同input所對應的所有路徑。
- state 慣用($q_0,q_1,q_3....$),可以使用自己定義的符號
- **==Regular Languages==**: A language $L$ is **regular**
- iff there exists some **DFA** $M$ such that $L=L(M)$
- $\text{Context-Free Languages} \supset
\text{Regular Langulars} \supset \text{Finite Languages}$
#### DFA Recap
有一個string input DFA 最後 Accept or Reject
- DFA做不到出現次數比較
- mod 可以做到
- DFA未必只有一種畫法
- 未必只有一維畫法、二維、多維...
- 電路執行都是DFA，可實作的
### NFA(Nondeterministic Finite Accepters)
:::success
- accept
- 所有的 input 被消耗
**and**
- 走到 final state
:::
:::danger
- reject
- 所有的 input 被消耗還沒走到 final state
**or**
- input 不能被消耗
:::
- Difference between DFA and NFA
- $\delta$ function
==$Q\times (\Sigma \cup\{\lambda\})\rightarrow2^Q$called transition function==
- $L(M)$ $M$ 是路徑可以到Final state
- 為什麼要有 NFA
- 比 DFA 更容易讀懂，比較好畫
- $\text{DFA} \equiv \text{NFA}$
- $\lambda$ 可以讓有規律的重複輸入更簡化，任意門
- $\lambda$ 不會出現在 input tape
- 無法電路實作
- 任一 NFA 可以被轉換成一個等效的 Single final state NFA
- 使用 $\lambda$
#### NFAs與DAFs是等效的
- Proof $L(M)_{NFA} = L(M')_{DFA}$
$\Longleftrightarrow$
$L(M) \subseteq L(M') \text{ and }L(M) \supseteq L(M')$
- NAF $\rightarrow$ DFA
- NFA walk = DAF walk 歸納法
- If the NFA has states $q_0, q_1 ,q_2...$
the DFA has states in the powerset :
$\{ \varnothing, \{q_0\}, \{q_1\}, \{q_0, q_1\}... \}$
#### Reduction of the Number of Statrs in FA$^*$
- 狀態越多，成本越高
- 簡化狀態
:::info
1. Remove all **inaccessible** states.==It is not to remove trap state==
2. Find all pairs.
3. Find all state whether state or final state, then we can distinguish some state.
4. Find remainder pair get input will go to which state.
5. Check above pair whether distinguishable?
:::
## Regular Expressions (RE)[wiki](https://en.wikipedia.org/wiki/Regular_expression#Syntax)
- language 三種方式
- Finite
- Descriptive (infinite)
- Using basic language operations
- 有*規律* 的字串*表達式*
- A regular expression is **not** a language.
- A regular expression 是用來描述 a regular language.
- It is incorrect to say that for a language $L$, $L = (a + b + c)^*$
- 大括弧$\{\}$
- But it’s okay to say that $L$ **is described by** $(a + b + c)^*$
:::warning
Let Σ be a given alphabet. Then
1. $\varnothing , \lambda, \text{ and }a \in \Sigma$ are all regular expressions.
These are called primitive regular expressions.
2. If r1 and r2 are regular expressions,
so are $r_1+r_2, r_1\cdot r_2, r_1^*\text{ and }(r_1)$.
3. A string is a regular expression **iff**
it can be derived from the primitive regular expressions
by a finite number of applications of the rules in (2).
==Regular Expressions 需要 primitive regular expressions 和 rules。==
:::
### Priority of Operators
1. $^*$
2. $\cdot$
3. $+$
- $L(r)$: Language generated by regular expression $r$
- 比較差異
- $L(G)$ ?
- $L(M)$ ?
- $L(r)$ ?
### Generalized Transition Graphs (GTG)
Find a regular expression capable of generating
the labels of all the walks from $q_0$ to any **final state**.
- $NFA \rightarrow RE$
- 感覺很複雜...，先補上所有的路徑，包含$\varnothing$，然後慢慢移除不需要的state。
### Regular Grammar
#### Grammar
- Linear
- Grammar中，每個過程中至多在箭頭右側出現一個變數
- Right-Linear Grammar
箭頭右側出現的變數在最右側
- Left-Linear Grammar
箭頭右側出現的變數在最左側
- non-Linear
#### What is Regular Grammar
- **Only** **Right-Linear** and **Left-Linear** are Regular Grammars.
- Regular grammars generate regular languages.
#### Proof
直接證明Right-Linear是簡單的。
直接證明Left-Linear不是那麼直觀，但我們可以利用Right-Linear的reverse來證明，
$L(G) \text{ is Right-Linear regular Grammar } L(G)^R...$
### Summary
```graphviz
digraph{
node[shape=box fixedsize=true width= 2 height= 0.5]
RE->DN
DN->RG
RG->DN
DN->RE
RE[label="Regular Expressions"]
DN[label="DFA／NFA"]
RG[label="Regular Grammars"]
}
```
- 先轉換成DFA or NFA 再做其他的轉換
## The Pumping Lemma
反證法
:::success
- Pick a string such that: $w\in L$, $|w|\geq m$
- Write: $w=\text{自己選定的string}= xyz$
- 因為Pumping Lemma，所以$|xy| \leq m, |y|\geq 1$
- Pick $xy^iz\in L ,i = 0,1,2,...$
- ...
:::
:::danger
- 並不是符合pumping lemma就是RE
- 關於判斷是否是RE[參見](https://reurl.cc/L6VEV4)
:::
- [CFL and Pumping Lemma](#Two_Pumping_Lemma)
## Example1
- $a,b$ 數量是偶數
```graphviz
digraph{
node[shape=circle fixedsize=true]
rankdir=LR
even[shape=doublecircle]
even->odd[label=a，b]
odd->even[label=a，b]
}
```
- $a$ 的數量是偶數，$b$ 的數量是奇數
```graphviz
digraph{
node[shape=circle fixedsize=true width=.7]
subgraph{
rank=same
rankdir=LR
pointer[shape=none label= ]
f[shape=doublecircle label="even a\nodd b"]
3[label="even a\neven b"]
}
subgraph{
rank=same
rankdir=LR
1[label="odd a\neven b"]
2[label="odd a\nodd b"]
}
pointer->3
1->2[label=b]
1->3[label=a]
2->1[label=b]
2->f[label=a]
3->1[label=a]
3->f[label=b]
f->2[label=a]
f->3[label=b]
}
```
- $(N_a-N_b) \bmod 3 =0$
```graphviz
digraph{
rankdir=LR
node[shape=circle fixedsize=ture]
pointer[label=" " shape=none]
pointer->0
0[shape=doublecircle]
subgraph{
1
2
}
subgraph{
-1
-2
}
0->1[label=a]
1->0[label=b]
1->2[label=a]
2->1[label=b]
2->0[label=a]
0->-1[label=b]
-1->0[label=a]
-1->-2[label=b]
-2->-1[label=a]
-2->0[label=b]
}
```
- $L=\{a^nb,n\geq0\}$
Find DFA accept $L^2$
- $L^2=\{a^nba^mb,n,m\geq0\}$
- find $L$
```graphviz
digraph{
node[shape=circle fixedsize=ture]
rankdir=LR
pointer[label=" " shape=none]
q0->q0[label="a"]
pointer->q0
q0->q1[label="b"]
q1[shape=doublecircle]
}
```
- find $L^2$
```graphviz
digraph{
node[shape=circle fixedsize=ture]
rankdir=LR
pointer[label=" " shape=none]
subgraph{
q0->q0[label="a"]
pointer->q0
q0->q1[label="b"]
}
subgraph{
q1->q1[label="a"]
q1->qf[label="b"]
qf[shape=doublecircle]
qf->q3[label="a,b"]
q3->q3[label="a,b"]
}
}
```
---
## Context-Free Language
$\text{Context-Free Languages} \supset
\text{Regular Langulars} \supset \text{Finite Languages}$
```graphviz
digraph{
node[shape=none]
graph[rankdir=RL]
Context_Free_Languages[fontcolor=red]
Context_Free_Grammars->Context_Free_Languages->Pushdown_Automata[dir=both]
}
```
:::warning
**Difference between Regular Expressions and Context-Free Grammar**
- CFG
> $\begin{align}
> exp\; &{\color{red}{\rightarrow}} \text{ exp } op \text{ exp}|(exp) |number\\
> op\; &{\color{red}{\rightarrow}} +|−|∗
> \end{align}$
- RE
> $\begin{align}
> number\; &{\color{red}{=}}\; digit\; digit^∗\\
> digit\; &{\color{red}{=}}\; 0|1|2|3|4|5|6|7|8|9
> \end{align}$
- CFG is **recursive**
:::
### Context-Free Grammars
- CFG is also called BNF (Backus-Naur Form 巴科斯範式) grammar
- From any context-free grammar **(which doesn’t produce $\lambda$)**
:::info
- $G = (V,T,S,P)$
- $V=$ Variables
- $T=$ Terminal symbols
- $S=$ Start variable
- $P=$ Productions of the form:產生式
- $A\rightarrow x$
- $A$ is a variable
- $x\in (V \cup T)^*$
- $A\rightarrow \lambda$ is a valid production
> We say that the grammar is **context-free**
> since 無論 A 在哪裡都可以被替換
**Notation**
- Notational conventions
- $a,b,c, ...$ denote symbols in $V_𝑡$
- $A,B,C, ...$ denote symbols in $V_𝑛$
- $U,V,W,...$ denote symbols in $V$
- $\alpha, \beta, \gamma, ...$ denote strings in $V^∗$
- $u,v,w, ...$ denote strings in $V_𝑡^∗$
:::
### Derivation (Parse) Trees
我們應該如何推論分析 context-free language
- Example: $A\rightarrow abABc$
- Derivation (Parse) Trees
```graphviz
digraph{
node[shape=circle]
parent_A[label=A]
parent_A->a
parent_A->b
parent_A->A
parent_A->B
parent_A->c
}
```
:::info
Let $G = (V, T, S, P)$ be a CFG. An ordered tree is a derivation tree for G
iff it has the following properties.
1. The root is labeled $S$
2. Every leaf has a label from $T \cup {λ}$
3. Every internal vertex has a label from $V$
4. If a vertex(node) has label $A \in V$,
and its children are labeled $a_1, a_2, …, a_n$,
then $P$ must contain a production $A \rightarrow a_1a_2…a_n$
5. A leaf labeled $λ$ has no sibling(手足)
:::
- Partial derivation tree
:::info
1. ~~The root is labeled $S$~~
2. Every leaf has a label from ${\color{red}{V} \cup T \cup {λ}}$
3. Every internal vertex has a label from $V$
4. If a vertex(node) has label $A \in V$,
and its children are labeled $a_1, a_2, …, a_n$,
then $P$ must contain a production $A \rightarrow a_1a_2…a_n$
5. A leaf labeled $λ$ has no sibling(手足)
:::
- Leftmost and Rightmost Derivations
- 每次替換都換最左邊會是最右邊的變數
- 有時候順序不重要，都會得到相同的結果
### Parsing and Ambiguity
- Derivation
- input: $aabb$
- Derivation: $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$
- Parsing
- 我們想知道，給定一個w他是否屬於L(G)
- :::danger
- $A\rightarrow B$
- $A\rightarrow \lambda$
:::
- 當我們在 Grammar 中，把以上的情況去除，我們可以將窮舉搜尋轉換成演算法
- 暴力解析
- Simple grammar **(s-grammar)**
- $A\rightarrow ax$
- $(A,a)$只出現一次
- $x$ is the string of variables
- ==Ambiguity==
- A context-free grammar is **ambiguous** if some string has:
**two or more derivation trees**
- leftmost or rightmost derivations
- bad,我們想要移除
- How to remove?
1. 指定意圖 (指定結合性和優先順序)
2. rewrite a grammar
- Another Ambiguous Grammar
- if then else
- Some context free languages have **only ambiguous grammars**
- How to show a language is ambiguous?
- 使用leftmost or rightmost derivations show two or more derivation trees
- ==Inherent Ambiguity==(固有)
- 有些context-free languages 一定有 ambiguous grammar
- $L=\{a^nb^nc^m\} \cup \{a^nb^mc^m\}$
- $a^nb^nc^n$ has two derivation trees
## Transforming Grammars
### 定理或工具
:::success
- $A\rightarrow x_1Bx_2$
- $B\rightarrow y_1|y_2|...|y_n$
- 替換
- $A\rightarrow x_1y_1x_2|x_1y_2x_2|...|x_1y_nx_2$
:::
:::info
- 使用時機 and remove step
1. Remove Nullable Variables
- $\lambda$ production : $A \rightarrow \lambda$
- Nullable Variable: $A \Rightarrow ... \Rightarrow \lambda$
2. Remove Unit-Productions
- $A\rightarrow B$
3. Remove ==Useless== Variables
- 不會結束的 derivations (Derive no terminal string)
- 從 $S$ 開始到不了 (Unreachable)
- A production $A\rightarrow x$ is useless **iff** any of its variables is useless
:::
:::success
- If $S \Rightarrow ... \Rightarrow xAy \Rightarrow ... \Rightarrow w,w\in L(G)$,
then variable is A useful
:::
### ==CNF==(Chomsky Normal Form)
:::info
- Form
- $A\rightarrow BC$，to 只有兩個變數
- $A\rightarrow a$，to terminal
:::
:::success
- 如何做到
- First remove:
- Nullable variables
- Unit productions
- 自定義新的變數
- 將 terminal 變成單一 variable $\rightarrow$ terminal
- 將兩個變數變成單一變數
:::
- For any context-free grammar(符合上述使用時機)there is an
**equivalent** grammar in **C**homsky **N**ormal **F**orm
- It is very **easy** to find the CNF for any context-free grammar
#### GNF(Greibach Normal Form)
:::info
- Form
- $A\rightarrow aV_1V_2V_3...V_n$ , $n\geq0$
- $a$ is a symbol
:::
- For any context-free grammar(which doesn’t produce $\lambda$ )there is an
**equivalent** grammar in **G**reibach **N**ormal **F**orm
- It is **hard** to find the GNF of any context-free grammar
### CYK Parser
> J. **C**ocke
> D. H. **Y**ounger
> T. **K**asami
- In CNF
- 列出 $V_{11},V_{22},...,V_{nn}$
$V_{12},V_{23},...,V_{n-1n}$
$...,V_{1n}$
$V_{ab} \text{，a 開始symbol，b 結束symbol}$
- bottom up 尋找對應的路徑
- The CYK algorithm can be easily converted to a parser (bottom up parser)
#### Membership Question
- For context-free grammar $G$ find if string $w\in L(G)$
- Membership Algorithms
- Exhaustive search parser: $O(P^{2|w|+1})$
- **CYK** parsing algorithm: $O(|w|^3)$
## PushDown Automata(PDA)
- 多一個stack，提供記憶性
- 可以實現$L=\{a^nb^n:n\geq0\}$
```graphviz
digraph{
node[shape=circle]
graph[rankdir=LR]
q1->q2[label=a，b，c（w）]
}
```
- $a$ : input symbol
- $b$ : pop symbol，當前 stack 最上面的 symbol
- $c$ : push symbol
- ${\color{red}{w}}$ : push string
- If $w=abc$，$a$ 放最上面
- stack 最底部為 $z$，可以pop，但
- The automaton Halts(停止) in state and **Rejects** the input string
> 不建議 pop $z$，若有需求則使用($\lambda,z,z$)
- Instantaneous Description (ID)瞬間描述
- $(q, u, s)$
- $q$ : Current state
- $u$ : Remaining input
- $s$ : Current stack contents
- $\vdash$ : The symbol denotes a move from one ID to another
- $\vdash ^*$ (\*應該放在正上方)：簡化多個 $\vdash$，方便
- No transition is allowed to be followed when the stack is empty
- ==不要把 stack 清空==
### Non-Determinism
- 可以接受
- $\lambda$ -transition
```graphviz
digraph{
node[shape=circle]
graph[rankdir=LR]
q1->q2[label=λ，b，c]
}
```
- 相同input **and** 相同 stack 值
```graphviz
digraph{
node[shape=circle]
graph[rankdir=LR]
q1->q2[label=a，b，c]
q1->q3[label=a，b，d]
}
```
:::success
- accept
- All the input is consumed **AND** The last state is a final state
:::
:::danger
- reject
- $\lnot$(All the input is consumed **AND** The last state is a final state)
- In other words
- The input cannot be consumed
**OR**
- The input is consumed and the last state is not a final state
**OR**
- *The stack head moves below the bottom of the stack*
:::
- 最後，我們==不在意 stack 裡面的內容==
#### $\text{Context-Free Languages (Grammars)} = \text{Languages Accepted by NPDAs}$
- Context-free to NPDA
- 寫出grammar
- 寫出NPDA
- 加上NPDA的中止條件
- 只有碰到終止條件NPDA指針改變
- 其餘都在記憶體中操作
:::info
- In **Greibach normal form**
- $A \rightarrow aV_1V_2...V_k$
- $A$：Top of stack
- $a$：Input
- $V_1V_2...V_k$：New Variable in stack
:::
- General
- $A\rightarrow w\Rightarrow\lambda,A,w$
- any terminal $a\Rightarrow a,a,\lambda$
```graphviz
digraph{
node[shape=circle]
graph[rankdir=LR]
q[label=start shape=none]
q->q0
q0->q1[label=λ，λ，S]
q1->q2[label=λ，z，z]
q1->q1[label=λ，A，w___a，a，λ]
}
```
- NPDA to context-free
- 可能只有是非題
- 先轉換成single final state and 當 accept 清空 stack
- 使用 $\lambda,\lambda,\lambda$ 拉出新的 state (在這裡清空stack)
- 特殊的 form
- 看到終止條件
- 讓 stack 多一個
- 讓 stack 少一個
- 實例
- 那個看起來很複雜的表
1. 寫出所有有可能的路徑
2. 刪掉不可能出現的
### Determinism
- ==不可以==接受non-deterministic choices
- some $\lambda$ -transition
- ${\color{red}{\lambda,\lambda,\lambda}}$
```graphviz
digraph{
node[shape=circle]
graph[rankdir=LR]
q1->q2[label=λ，b，w1]
q1->q3[label=a，b，w2]
}
```
- 相同input **and** 相同 stack 值
```graphviz
digraph{
node[shape=circle]
graph[rankdir=LR]
q1->q2[label=a，b，c]
q1->q3[label=a，b，d]
}
```
- ${\color{red}{\text{NPDAs Have More Power than DPDAs}}}$
- 跟 DFA 與 NFA 關係不同
:::warning
- stack 記憶性只能用一次
- 證明較困難，可以嘗試理解、記得誰是不是 context free
:::
## Two_Pumping_Lemma
- 若 $L$ 是上下文無關語言，則存在一常數 $m>0$ 使得語言 $L$ 中每個字串 $w$ 的長度 $|w| \geq m$
:::info
- Pick $w = \text{any string}$
- Pick $w \in L$ and $|w|\geq m$
- write $w=uvxyz$，and $|vxy|\leq m$ and $|vy|\geq 1$
- $(|w|\geq m \geq |vxy|)$
- Pumping Lemma says: $uv^ixy^iz \in L$ for all $i \geq 0$
- 我們檢查 $vxy$ 在 $w$ 之中所有的位置
:::
### Proof of Pumping Lemma
:::success
- Proof $k > \text{number of productions}$
- then some production must be repeated
- $f$ : 最大的 right side of a production
- $p=\text{number of productions}\times f$
- $m=p+1$ 最多有可能的 state
1. $V_1\Rightarrow V_2 \Rightarrow ... V_k \Rightarrow w$
2. $|V_{i+1}|\leq|V_i|+f$
3. $|w|< kf$
4. $m\leq |w| \leq kf$
5. $p < kf\Rightarrow k > {p \over f}$
6. **at least a variable is repeated by itself**
:::
:::success
- Proof of Lemma1
- 由 CNF 的定義，$m$ 個 variable 將可以產生 $2^{m-1}$ 個 terminals
```graphviz
graph{
node[shape = circle]
S--A
S--B
A--T1
A--T2
B--T3
B--T4
}
```
:::
## Turing Machine
- ${\color{red}{\text{Language}}}\supset\text{Turing Machines}\supset
\text{Context-Free Languages} \supset
\text{Regular Langulars} \supset \text{Finite Languages}$
- 目前沒有能超越 Turing Machines 的工具，但能確定外面仍有不能 accept 的 Language
- 只能接受 Determinism
- example
- 走到 final state 就終止且 accept
- 不能從 final state 走出來
```graphviz
digraph{
node[shape=circle]
graph[rankdir=LR]
q1->q2[label="a,b,R/L"]
}
```
- $(a,b,R/L)$
- $a$ 讀到的值
- $b$ 改成什麼
- $R/L$ 指針要往哪裡走
- Acceptance
- Accept
- If machine halts in a **final state**
- Reject
- If machine halts in a **non-final state**
or
If machine enters an **infinite loop**
- Infinite loop
- The final state cannot be reached
- The machine never halts
- The input is not accepted
- What is Standard Turing Machine
- Deterministic
- Infinite tape in both directions
- Tape is the input/output file
- Computing Functions
- ==Turing Thesis==
:::info
- 目前只要問題能用演算法寫出來，Turing machine 都可以解決
- Turing machine 是目前最 powerful 的機器
:::
### 不同變形的Turing Machine
- 不同變形的 Turing machine 可以讓速度比標準的 machine 更快速
- 但不會 more powerful
- original machine 中的每一步都可以對應到 Simulation Machine 中的其中一步
- (x) 現在的computer 能不能解決所有演算法
- 現在的 computer 不是雙邊無窮的tape
- 兩個 semi-infinite 可以組成標準形式
- Left part
- Right part
- off-line
- 將 input and tape 用四條 Standard machine 來模擬
- 其中兩條紀錄 input or tape 的指針位置，由 $0,1$ 表示
- Same power doesn’t imply same speed
---
- Non-Determinism 想法可能跟量子電腦相關
- turing machine 是 countable
- There are more languages than Turing Machines
- 有 Language 沒辦法被描述
- Uncountable Sets
- 利用反證法
- $t_i$ 取出 第 $i$ 個組成新的 string 取反
- 假設會出現在這個 string 會出現 $t_i$ 這件事不可能發生
- 因為第 $i$ 個會跟這個 string 的第 $i$ 個相反，理論上要一樣
- LBA’s have more power than NPDA’s
- ==LBA’s have also less power than Turing Machines==
Sign in with Wallet
Connect another wallet