確定的有限自動機(definite automata, DFA)
1. 定義
確定的有限自動機 是一個五元組：
-
是輸入符號的有窮集合拟赊；
-
是狀態(tài)的有限集合具壮；
-
是初始狀態(tài)；
-
是終止狀態(tài)集合，
；
-
是
到
2. DFA示意圖
處在狀態(tài)
3. 狀態(tài)轉(zhuǎn)換圖
映射可以由狀態(tài)變換圖描述。
為了明確起見，終止狀態(tài)用雙圈表示合是，起始狀態(tài)用有“開始”標記的箭頭表示了罪。如:
4. DFA 定義的語言
如果一個句子 使得有限自動機
有
，那么聪全，稱句子
被
接受泊藕。
由 定義的語言
就是被
接受的句子的全集。即：
-
例子：
鏈被
接受难礼。
= {含偶數(shù)個
和偶數(shù)個
的鏈}
不確定的有限自動機(non-definite automata, NFA)
1. 定義
不確定的有限自動機 是一個五元組：
-
-
-
-
-
的映射谦炬。
DFA與NFA
1. DFA與NFA的唯一區(qū)別
NFA 與 DFA 的唯一區(qū)別是：在 NFA中 是一個狀態(tài)集合悦屏，而在 DFA 中
是一個狀態(tài)。
- 例子
該自動機為不確定自動機键思；句子可以被接受础爬。
1. DFA與NFA的關(guān)系
設(shè) 是一個被 NFA 所接受的句子的集合，則存在一個 DFA它能夠接受
吼鳞。
正則文法與有限自動機的關(guān)系
1. 正則文法 
自動機
定理
若是一個正則文法幕帆，則存在一個有限自動機
，使得：
赖条。
由
構(gòu)造
(1) 令，其中纬乍，
是一個新增加的非終結(jié)符碱茁。
(2) 如果在中有產(chǎn)生式
，則
仿贬，否則
纽竣。
(3) 如果在，
茧泪，
蜓氨，則
。
(4) 如果在, 則
(5) 對于每一個嗜侮。
1. 自動機 正則文法
定理
若啥容。
由
(1) 令咪惠；
(2) 如果遥昧，則在
；
(3) 如果渠鸽，則在
