下推自動機

下推自動機PDA的模型是由一條輸入帶,一個有窮控制器和一個下推棧組成。

因素

PDA的動作由三個因素決定:(1)當前所處狀態
(2)讀頭所指符號;(3)下推棧棧頂符號
定義:PDA定義為一七元組
M=(Q,,H,,q0,z0,F),其中:
Q為控制器的有窮狀態集;
是一個有窮字母表;
q0Q是控制器的初始狀態
H是下推字母表;
Z0H是下推棧的初始符;
FQ是一終止狀態集;
是轉換函式,是在 Q({})HQH*的映射。轉換函式為:
(q,a,z)={(q1,1),(q2,2),…(qn,n)}
其中q,qiQ,a*,zH。其意義是,控制器當前狀態為q,下推棧棧頂符號為z,輸入符號為a(可為)情況下,狀態轉換到序偶集。這個序偶集由(qi,i)組成,其中qi下一狀態,i為代替z的棧頂符號串,注意要用i的逆串放入棧中。
推自動機和上下文無關文法
設有文法G【A】:
AA(A)
不難看出該文法對應的語言是成對括弧串的集合,如
(),(()),()(),(()())(),(()(()))……
能識別該文法定義的語言的自動機為:
(( ( (
S0 S1S2 …. Sn
)) ) )
顯然該自動機只能識別嵌套層數為K的成對括弧串,若增加了一層嵌套,則需要在自動機的右端增加一個新的狀態,隨著嵌套層次的增加,狀態要增加

相關詞條

相關搜尋

熱門詞條

聯絡我們