# 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

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

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*```
```
``````Chapter 2 : Turing Machine
Theorem : Single tape TM can simulate TM in O(f(n)^2)

Linear speedup :
if L in TIME(f(n)) then ε>0,L in TIME(εf(n)+n+2)

Nondeterministic Turing Machine
M = (K,Σ,Δ,S)
K : set of state
Σ: finite set of symbol
s : s in K, initial state
Δ: (K*Σ)*[(K∪{h,”yes”,”no”})* Σ*{←,—,→}]
(it’s a relation)

if path, M(x;path) = “yes” then M accept x
else M reject x
if x,path M(x;path) & |path|<(f(|x|) then M decide x in f(|x|)

Complexity of Nondeterministic Turing Machine
M accept x => T(M(x)) = 所有 “yes” path中最短的 path長度。
M reject x => T(M(x)) = 整棵tree的大小。

Universal Turing Machine
U(M;x) : simulate TM M on input x
encode : M = (K,Σ,Δ,S)
K = {|Σ|+1, |Σ|+2,.., |Σ|+|K|}
where
s         = |Σ|+1
←         = |Σ|+|K|+1
—        = |Σ|+|K|+2
→        = |Σ|+|K|+3
yes    = |Σ|+|K|+4
no        = |Σ|+|K|+5
h        = |Σ|+|K|+6

tape 1: (input)           M ; x
tape 2: (configuration) (s, >, x) in initial state
(w, q, u) in middle state```
```

# 圖靈-邱奇假說

Turing Machine Powerful Thesis (Church)

1. There is no formalism to model any mechanical calculus that is more powerful than Turing Machine and equivalent formalisms.
2. Any algorithm can be coded in term of a Turing Machine.

Chapter 2 : Turing Machine
Theorem : Single tape TM can simulate TM in O(f(n)^2)

Linear speedup :
if L in TIME(f(n)) then ε>0,L in TIME(εf(n)+n+2)

# Nondeterministic Turing Machine

M = (K,Σ,Δ,S)
K : set of state
Σ: finite set of symbol
s : s in K, initial state
Δ: (K*Σ)*[(K∪{h,”yes”,”no”})* Σ*{←,—,→}]
(it’s a relation)

if path, M(x;path) = “yes” then M accept x
else M reject x
if x,path M(x;path) & |path|<(f(|x|) then M decide x in f(|x|)

# Complexity of Nondeterministic Turing Machine

M accept x => T(M(x)) = 所有 “yes” path中最短的 path長度。
M reject x => T(M(x)) = 整棵tree的大小。

# Universal Turing Machine

U(M;x) : simulate TM M on input x
encode : M = (K,Σ,Δ,S)
K = {|Σ|+1, |Σ|+2,.., |Σ|+|K|}
where
s = |Σ|+1
← = |Σ|+|K|+1
— = |Σ|+|K|+2
→ = |Σ|+|K|+3
yes = |Σ|+|K|+4
no = |Σ|+|K|+5
h = |Σ|+|K|+6

tape 1: (input) M ; x
tape 2: (configuration) (s, >, x) in initial state
(w, q, u) in middle state