下推自動機(push-down automata, PDA)
1. 定義
PDA 可以看成是一個帶有附加的下推存儲器的有限自動機，下推存儲器是一個棧。如下圖所示：
定義如下：
一個不確定的PDA可以表達成一個7元組：
-
是輸入符號的有窮集合；
-
是狀態(tài)的有限集合；
-
是初始狀態(tài)；
-
為下推存儲器符號的有窮集合；
-
為最初出現(xiàn)在下推存儲器頂端的符號;
-
是終止?fàn)顟B(tài)集合,
-
是從
到
子集的映射。
2. 映射關(guān)系 的解釋
3. 符號約定
4. 下推自動機接受的語言
下推自動機 所接受的語言定義為：
5. 舉例
下推自動機接受語言
，其中，
,
定義如下:
那么：
另外兩種自動機
1. 圖靈機
- 圖靈機與0型文法等價；
- 圖靈機與有限自動機(FA)的區(qū)別：圖靈機可以通過其讀/寫頭改變輸入帶的字符。
2. 線性帶限自動機
- 線性帶限自動機與1型文法等價；
- 線性帶限自動機是一個確定的單帶圖靈機，其讀寫頭不能超越原輸入帶上字符串的初始和終止位置，即線性帶限自動機的存儲空間被輸入符號串的長度所限制。
各類自動機的區(qū)別
各類自動機的主要區(qū)別是它們能夠使用的信息存儲空間的差異：有限狀態(tài)自動機只能用狀態(tài)來存儲信息；下推自動機除了可以用狀態(tài)以外，還可以用下推存儲器(棧)；線性帶限自動機可以利用狀態(tài)和輸入/輸出帶本身。因為輸入/輸出帶沒有“先進后出”的限制，因此，其功能大于棧；而圖靈機的存儲空間沒有任何限制。
語言與識別器的對應(yīng)關(guān)系
識別器是有窮地表示無窮語言的另一種方法。每一個語言的句子都能被一定的識別器所接受。
