自動機理論中,下推自動機(英語:Pushdown automaton)是使用了包含數據的有限自動機

綜述

編輯

下推自動機比有限自動機複雜:除了有限狀態組成部分外,還包括一個長度不受限制的;下推自動機的狀態遷移不但要參考有限狀態部分,也要參照當前的狀態;狀態遷移不但包括有限狀態的變遷,還包括一個的出棧或入棧過程。下推自動機可以形象的理解為,藉由加上讀取一個容量無限的能力,擴充一個能做 -轉移的非確定有限自動機

下推自動機存在「確定」與「非確定」兩種形式,兩者並不等價。(對有限自動機兩者是等價的)

每一個下推自動機都接受一個形式語言。被「非確定下推自動機」接受的語言是上下文無關語言

如果我們把下推自動機擴展,允許一個有限自動機存取兩個,我們得到一個能力更強的自動機,這個自動機與圖靈機等價。

下推自動機作為一個形式系統最早於1961年出現在 Oettinger 的論文中。它與上下文無關文法的等價性是由喬姆斯基於1962年發現的。

形式定義

編輯

PDA 形式定義為 6-元組:

  這裏的

  •  狀態的有限集合
  •   是輸入字母表的有限集合
  •  字母表的有限集合
  •  :  轉移函數
  •   是「開始狀態」
  •   是「接受狀態」的集合
  •  
  •  

計算定義 1

對於任何 PDA  ,計算路徑是一個有序的(n+1)-元組  ,這裏的  ,它滿足如下條件:

(i)   對於 i = 0, 1, 2,......, n-1,

這裏的  

(ii)   使得

 

在直覺上,PDA 在計算過程中任何一點上都面對着多種可能性,從棧頂讀一個符號並把它替代為另一個符號,從棧頂讀一個符號並刪除它而不替換,不從棧頂讀任何符號但壓入另一個符號進去,或什麼都不做。所有這些都同時由等式    來支配。  是緊接在第 i+1 次轉移移動之前的棧內容,而   是要從棧頂去除的符號。  是緊接在第 i+1 次轉移移動之後棧內容,而   是在第 i+1 次轉移移動期間要增加到棧上的符號。

   二者都可以  

如果   ,則 PDA 從棧讀一個符號並把它替代為另一個符號。

如果   ,則 PDA 從棧讀一個符號並刪除它而不替換。

如果   ,則 PDA 簡單的增加一個符號到棧上。

如果   ,則 PDA 保持棧不變動。

注意當 n=0 時,計算路徑就是單元素集合  

計算定義 2

對於任何輸入  ,M 接受 w,如果存在計算路徑   和有限序列  ,使得

(i) 對於每個 i = 0, 1, 2,...m,  都在計算路徑上。就是說

  這裏的   使得  

(ii)   對於每個 i = 0, 1, 2,...m-1。

這裏的    定義同於計算定義 1。

(iii)  ,如果  

這裏的    定義同於計算定義 1。

(iv)   

注意上述定義不提供測試空棧的機制。要這麼做你需要在所有計算開始前在棧上寫一個特殊符號,使得 PDA 可以在檢測到這個符號的時候有效的識別出棧已經空了。形式的說,實現它可通過介入轉移  這裏的 $ 是特殊符號。

例子

編輯

下面是識別語言   的 PDA 的形式描述:

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •   對於任何其他狀態、輸入和棧符號的值。

理解計算過程

編輯

下面展示上述 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 =  
設置 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) =  
因此計算在 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,  )
 
 (pm-1,  , xm)   (pm,  )
 (pm,  ,   )   (pm+1, yn)
 (pm+1,  ,   )   (pm+2, yn-1)
 
 (pm+n-1,  ,   )   (q2, y1)

參見

編輯

外部連結

編輯

參考書目

編輯