自動機理論
1.自動機概念
自動機是語言和串的識别裝置；同時，自動機也是從識别的觀點來定義語言的一種方法。
用能夠被某種識别裝置所接受的串的集合來定義語言，記為L(A)。
2.Chomsky文法模型對應的自動機模型
3.有限自動機
- 有限自動機概述
有限自動機是最簡單的語言識别裝置，有限自動機隻能處理正則文法所産生的語言。
- 有限自動機組成
狀态寄存器，隻讀頭，輸入帶
- 有限自動機模型
- 有限自動機的運作模型
狀态寄存器的狀态——目前狀态q
從輸入帶讀入一個字元——目前字元t
由q和t映射到一個新的狀态——新狀态q’
- 有限自動機語言
- 有限自動機定理
當且僅當一個語言是由正則文法産生時，該語言可以用有限自動機來識别。
- 自動機識别問題描述
已知文法G = (VN, VT, P, S)，如何構造等價有限自動機Af= (Q, Σ, δ, q0, F)？
使L(Af) = L(G)；
- 通過文法四元式構造等價有限自動機的規則
已知上下文無關文法G = (VN, VT, P, S)
–求等價Ap= (Q, Σ, δ, q0, F)
1.每個非終止符号對應一個狀态
VN= { X0, X1, X2, ……, Xn }；
Q = { q0, q1, q2, ……, qn, qn+1 }；
其中X0是起始符S，qn+1是附加狀态且F = { qn+1 }；
2.每個産生式對應一個映射
Xi→aXj，δ(qi, a) = { … qj…}；
Xi→a，δ(qi, a) = { … qn+1…}；
- 有限自動機的狀态轉移圖
列出所有狀态，用連線表示狀态映射。下面說一個例子
以上就是與3形文法對應的有限自動機的概念和構造方式。