Finite state automata :
M = (K, Σ, δ, S, F)
K : set of state
Σ: finite set of input symbol
s : s in K, initial state
δ: (K*Σt*Σs)->K * Σ*
F : F in K, final state set
regular expression :
A->wB, A->w
Pumping lemma for regular expression
if z in L and |z| >= n, we may write z = uvw
1. |v| >= 1
2. |uv| <= n
3. i uviw in L
Theorem : L(Finite state automata) = L(Regular expression)
Push down automata
M = (K, Σi, Σs, δ, s, F)
K : set of state
Σi: finite set of input symbol
Σs: finite set of stack symbol
s : s in K, initial state
δ: (K * Σi * Σs)-> K * Σ*
F : F in K, final state set
Context free grammar :
G = (V,T,P,S)
A->α, αin (V∪T)*
Pumping lemma for context free grammar :
if z in L and |z| >= n, we may write z = uvwxy
1. |vx| >= 1
2. |vwx| <= n
3. i uviwxiy in L
Turing Machine (TM)
M = (K,Σ,δ,S)
K : set of state
Σ: finite set of symbol
s : s in K, initial state
δ: (K*Σ)->(K∪{h,”yes”,”no”})* Σ*(←,—,→)
example : A TM that decide plaindromes
plaindromes (迴文) : 正讀倒讀都一樣的 word。
K Σ δ
s 0 (q0 ,> ,→) s :start,q0:上次讀的bit為0.
s 1 (q1 ,> ,→) q1: 上次讀的bit為1.
s > (s ,> ,→) 寫上一個 >
s _ (yes,_ ,—)
q0 0 (q0 ,0 ,→) q0:移到最後一個bit “_”
q0 1 (q0 ,1 ,→)
q0 _ (q0’,_ ,←)
q1 0 (q1 ,0 ,←) q1:移到最後一個bit “_”
q1 1 (q1 ,1 ,←)
q1 _ (q1’,_ ,←)
q0’ 0 (q ,_ ,←) q0’: 看看是否為0
q0’ 1 (no ,1 ,—)
q0’ > (yes,_ ,→)
q1’ 0 (no ,1 ,—) q1’: 看看是否為1
q1’ 1 (q ,_ ,←)
q1’ > (yes,> ,→)
q 0 (q ,0 ,←) q : 回到開頭，繼續檢查下一個。
q 1 (q ,1 ,←)
q > (s ,> ,→)
Unrestricted Grammar
α->β
Theorem : L(Turing Machine) = L(Unrestricted Grammar)
L(Turing Machine) = L(First Order Logic)
Church-Turing Thesis :
“Computable function” can be identified with the class of partial recursive functions.
Closure Property :
A class of languages is closed under a particular operatio.
Example :
intersection : L1∩L2
union : L1∪L2
concatenation : L1L2
Kleene operator : L1*
