下推自動(dòng)機(jī)(push-down automata, PDA)
1. 定義
PDA 可以看成是一個(gè)帶有附加的下推存儲(chǔ)器的有限自動(dòng)機(jī)菩帝，下推存儲(chǔ)器是一個(gè)棧笛园。如下圖所示：
定義如下：
一個(gè)不確定的PDA可以表達(dá)成一個(gè)7元組：
-
是輸入符號(hào)的有窮集合尝哆；
-
是狀態(tài)的有限集合绊含；
-
是初始狀態(tài)市殷；
-
為下推存儲(chǔ)器符號(hào)的有窮集合纫事；
-
為最初出現(xiàn)在下推存儲(chǔ)器頂端的符號(hào);
-
是終止?fàn)顟B(tài)集合,
-
是從
到
子集的映射渗鬼。
2. 映射關(guān)系 的解釋
3. 符號(hào)約定
4. 下推自動(dòng)機(jī)接受的語(yǔ)言
下推自動(dòng)機(jī) 所接受的語(yǔ)言定義為：
5. 舉例
下推自動(dòng)機(jī)接受語(yǔ)言
览露，其中，
,
定義如下:
那么：
另外兩種自動(dòng)機(jī)
1. 圖靈機(jī)
- 圖靈機(jī)與0型文法等價(jià)肛循；
- 圖靈機(jī)與有限自動(dòng)機(jī)(FA)的區(qū)別：圖靈機(jī)可以通過(guò)其讀/寫(xiě)頭改變輸入帶的字符。
2. 線性帶限自動(dòng)機(jī)
- 線性帶限自動(dòng)機(jī)與1型文法等價(jià)银择；
- 線性帶限自動(dòng)機(jī)是一個(gè)確定的單帶圖靈機(jī)多糠，其讀寫(xiě)頭不能超越原輸入帶上字符串的初始和終止位置，即線性帶限自動(dòng)機(jī)的存儲(chǔ)空間被輸入符號(hào)串的長(zhǎng)度所限制浩考。
各類(lèi)自動(dòng)機(jī)的區(qū)別
各類(lèi)自動(dòng)機(jī)的主要區(qū)別是它們能夠使用的信息存儲(chǔ)空間的差異：有限狀態(tài)自動(dòng)機(jī)只能用狀態(tài)來(lái)存儲(chǔ)信息夹孔；下推自動(dòng)機(jī)除了可以用狀態(tài)以外，還可以用下推存儲(chǔ)器(棧)析孽；線性帶限自動(dòng)機(jī)可以利用狀態(tài)和輸入/輸出帶本身搭伤。因?yàn)檩斎?輸出帶沒(méi)有“先進(jìn)后出”的限制，因此袜瞬，其功能大于棧怜俐；而圖靈機(jī)的存儲(chǔ)空間沒(méi)有任何限制。
語(yǔ)言與識(shí)別器的對(duì)應(yīng)關(guān)系
識(shí)別器是有窮地表示無(wú)窮語(yǔ)言的另一種方法邓尤。每一個(gè)語(yǔ)言的句子都能被一定的識(shí)別器所接受拍鲤。
