在自動機理論中,下推自動機(英語:Pushdown automaton)是使用了包含數據的棧的有限自動機。
綜述
下推自動機比有限自動機複雜:除了有限狀態組成部分外,還包括一個長度不受限制的棧;下推自動機的狀態遷移不但要參考有限狀態部分,也要參照棧當前的狀態;狀態遷移不但包括有限狀態的變遷,還包括一個棧的出棧或入棧過程。下推自動機可以形象的理解為,藉由加上讀取一個容量無限棧的能力,擴充一個能做
-轉移的非確定有限自動機。
下推自動機存在「確定」與「非確定」兩種形式,兩者並不等價。(對有限自動機兩者是等價的)
每一個下推自動機都接受一個形式語言。被「非確定下推自動機」接受的語言是上下文無關語言。
如果我們把下推自動機擴展,允許一個有限自動機存取兩個棧,我們得到一個能力更強的自動機,這個自動機與圖靈機等價。
下推自動機作為一個形式系統最早於1961年出現在 Oettinger 的論文中。它與上下文無關文法的等價性是由喬姆斯基於1962年發現的。
形式定義
PDA 形式定義為 6-元組:
這裡的
是狀態的有限集合
是輸入字母表的有限集合
是棧字母表的有限集合
:
是轉移函數
是「開始狀態」
是「接受狀態」的集合
![{\displaystyle \Gamma _{\epsilon }=\Gamma \cup \{\epsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e1dd8bbc36510aa162a11e56faf48c7dd49fb84)
![{\displaystyle \Sigma _{\epsilon }=\Sigma \cup \{\epsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/951cb1411c5f7ed71247c9035a87b7a1e30330ff)
計算定義 1
對於任何 PDA
,計算路徑是一個有序的(n+1)-元組
,這裡的
,它滿足如下條件:
(i)
對於 i = 0, 1, 2,......, n-1,
- 這裡的
![{\displaystyle w_{i+1}\in \Sigma _{\epsilon },\ a_{i+1},\ b_{i+1}\in \Gamma _{\epsilon }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bc985ceb36f42142321edb0890057a1c352f13e)
(ii)
使得
![{\displaystyle s_{i}=a_{i+1}t_{i},\,s_{i+1}=b_{i+1}t_{i},\,t_{i}\in \Gamma ^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a34cb393779732ad335c4fe56c6cf7c6a8da321)
在直覺上,PDA 在計算過程中任何一點上都面對着多種可能性,從棧頂讀一個符號並把它替代為另一個符號,從棧頂讀一個符號並刪除它而不替換,不從棧頂讀任何符號但壓入另一個符號進去,或什麼都不做。所有這些都同時由等式
和
來支配。
是緊接在第 i+1 次轉移移動之前的棧內容,而
是要從棧頂去除的符號。
是緊接在第 i+1 次轉移移動之後棧內容,而
是在第 i+1 次轉移移動期間要增加到棧上的符號。
和
二者都可以
。
如果
而
,則 PDA 從棧讀一個符號並把它替代為另一個符號。
如果
而
,則 PDA 從棧讀一個符號並刪除它而不替換。
如果
而
,則 PDA 簡單的增加一個符號到棧上。
如果
而
,則 PDA 保持棧不變動。
注意當 n=0 時,計算路徑就是單元素集合
。
計算定義 2
對於任何輸入
,M 接受 w,如果存在計算路徑
和有限序列
,使得
(i) 對於每個 i = 0, 1, 2,...m,
都在計算路徑上。就是說
這裡的
使得 ![{\displaystyle r_{i}=q_{f(i)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b6da8380b8f18a037da79796119509470923150)
(ii)
對於每個 i = 0, 1, 2,...m-1。
- 這裡的
和
定義同於計算定義 1。
(iii)
,如果
- 這裡的
和
定義同於計算定義 1。
(iv)
且
注意上述定義不提供測試空棧的機制。要這麼做你需要在所有計算開始前在棧上寫一個特殊符號,使得 PDA 可以在檢測到這個符號的時候有效的識別出棧已經空了。形式的說,實現它可通過介入轉移
這裡的 $ 是特殊符號。
例子
下面是識別語言
的 PDA 的形式描述:
![{\displaystyle Q=\{q_{1},q_{2},q_{3},q_{4}\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db3d498a9bf30715b836a0a721c9c8dd91a6d0ea)
![{\displaystyle \Sigma =\{0,1\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7bbf2d1a9a4742d6b0aed0ee9b7b4b2df2a4072)
![{\displaystyle \Gamma =\{0,\$\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd1fbe291b92801afa0589a1ba4951c84f7d0418)
![{\displaystyle F=\{q_{1},q_{4}\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1481510379a9f9b733bb63dd829914b197327ed)
![{\displaystyle \delta (q_{1},\epsilon ,\epsilon )=\{(q_{2},\$),(q_{1},\epsilon )\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f776504f4cc013303240cb966f65074d9741ea39)
![{\displaystyle \delta (q_{2},0,\epsilon )=\{(q_{2},0)\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b8e4485e24fda65420b2bd52852b3eb6e999e93)
![{\displaystyle \delta (q_{2},1,0)=\{(q_{3},\epsilon )\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fc85af8654a6afbcac602f6b5e2ced3fb045835)
![{\displaystyle \delta (q_{3},1,0)=\{(q_{3},\epsilon )\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a7b9a6eb33fe0521082112755eb193e7e899c56)
![{\displaystyle \delta (q_{3},\epsilon ,\$)=\{(q_{4},\epsilon )\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e24c07d9763c637b89f30451bb8488f75e7675bd)
對於任何其他狀態、輸入和棧符號的值。
理解計算過程
下面展示上述 PDA 如何計算不同的輸入字符串。
(a) 輸入字符串 = 0011
- (i) 寫
(q1,
,
)
(q2, $) 來表示 (q2, $)
(q1,
,
)
- s0 =
, s1 = $, t =
, a =
, b = $
- 設置 r0 = q2
- (ii)
(r0, 0,
) =
(q2, 0,
)
(q2, 0)
- s1 = $, a =
, t = $, b = 0, s2 = 0$
- 設置 r1 = q2
- (iii)
(r1, 0,
) =
(q2, 0,
)
(q2, 0)
- s2 = 0$, a =
, t = 0$, b = 0, s3 = 00$
- 設置 r2 = q2
- (iv)
(r2, 1, 0) =
(q2, 1, 0)
(q3,
)
- s3 = 00$, a = 0, t = 0$, b =
, s4 = 0$
- 設置 r3 = q3
- (v)
(r3, 1, 0) =
(q3, 1, 0)
(q3,
)
- s4 = 0$, a = 0, t = $, b =
, s5 = $
- (vi)
(q3,
, $)
(q4,
)
- s5 = $, a = $, t =
, b =
, s6 = ![{\displaystyle \epsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3837cad72483d97bcdde49c85d3b7b859fb3fd2)
- 設置 r4 = q4
- 因為 q4 是接受狀態,0011 被接受。
- 作為總結,計算路徑 = (q1, q2, q2, q2, q3, q3, q4)
- 而 (r0, r1, r2, r3, r4) = (q2, q2, q2, q3, q4)
(b) 輸入字符串 = 001
- 計算移動 (i), (ii), (iii), (iv) 將必定同於情況 (a),否則,PDA 在到達 (v) 之前就已經進入死胡同。
- (v)
(r3,
, a) =
(q3,
, a)
- 因為 s4 = 0$,要麼 a =
要麼 a = 0
- 在任何一種情況下,
(q3,
, a) = ![{\displaystyle \varnothing }](https://wikimedia.org/api/rest_v1/media/math/render/svg/00595c5e33692e724937fdcc8870496acce1ac74)
- 因此計算在 r3 = q3 進入死胡同,這不是接受狀態。所以 001 被拒絕。
(c) 輸入字符串 =
- 設置 r0 = q1, r1 = q1
(r0,
,
)
(q1,
)
- 因為 q1 是接受狀態,
被接受。
廣義下推自動機(GPDA)
GPDA 是在一個步驟內寫入整個字符串到棧上或從棧上去除整個字符串的 PDA。
GPDA 形式定義為 6-元組
- 這裡的 Q,
,
, q0 和 F 的定義同於 PDA。
:
是轉移函數。
GPDA 的計算規則同於 PDA,除了 ai+1 和 bi+1 現在是字符串而不是符號之外。
GPDA 和 PDA 是等價的,如果一個語言可被一個 PDA 識別,它也可被一個 GPDA 識別,反之亦然。
可以使用下列模擬公式化對 GPDA 和 PDA 的等價性的一個分析式證明:
設
(q1, w, x1x2...xm)
(q2, y1y2...yn) 是 GPDA 的轉移。
這裡的 q1, q2
Q, w
, x1x2...xm
, m
0, y1y2...yn
, n
0。
構造 PDA 的下列轉移:
(q1, w, x1)
(p1,
)
(p1,
, x2)
(p2,
)
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083)
(pm-1,
, xm)
(pm,
)
(pm,
,
)
(pm+1, yn)
(pm+1,
,
)
(pm+2, yn-1)
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083)
(pm+n-1,
,
)
(q2, y1)
參見
外部連結
參考書目
|
---|
| | | 每個語言範疇都是其直接上面的範疇的真子集 每個語言範疇內的語言都可以用同一行的文法和自動機表示 |
|