對於Σ= {0,1,2}上的上下文無關文法G,其中起始變量S:
S→0S0 | 1S1 | 2S2 | Ÿ
Ÿ→22對於上下文無關語法,我如何將它轉換爲等價的下推自動機?
我如何變成一個相當於下推自動機
對於Σ= {0,1,2}上的上下文無關文法G,其中起始變量S:
S→0S0 | 1S1 | 2S2 | Ÿ
Ÿ→22對於上下文無關語法,我如何將它轉換爲等價的下推自動機?
我如何變成一個相當於下推自動機
一個下推自動機可以在堆棧的頂部推符號,彈出他們關閉此。它也可以將其轉換置於最上面的堆棧符號上。我們需要考慮一種機制,讓我們通過操縱我們的堆棧來接受正確的語言。
你的語法生成的語言,有以下特點:
22
這是一個迴文超過{0, 1, 2}
。也就是說,它向後讀取相同的向前。我們需要「記住」字符串的開頭,以便我們能夠判斷字符串的末尾是否向後重複。對於堆棧來說,這是一個很好的用例:我們可以在看到它們時將這些符號推入堆棧,然後在我們讀取它們時將它們彈出。另一個說明:我們知道我們只能在閱讀22
之後嘗試開始閱讀。
首先,我們讀到的一切,把它壓入堆棧,直到找到「22」:
Q s S Q' S'
----------------------
// read 0s and 1s and push them on the stack
q0 0 Z q0 0Z
q0 0 0 q0 00
q0 0 1 q0 01
q0 1 Z q0 1Z
q0 1 0 q0 10
q0 1 1 q0 11
// if you read a 2, pus it on the stack and
// go to a new state where we look for a second 2
q0 2 Z q1 2Z
q0 2 0 q1 20
q0 2 1 q1 21
// if you read a 2 and then 0 or 1, go back to the
// initial state and keep reading input. otherwise,
// if you find a second two, proceed
q1 0 2 q0 02
q1 1 2 q0 12
q1 2 2 q2 22
// assume the '22' we just saw was not the one in
// the middle of the input string and that we need
// to keep reading input.
q2 0 2 q0 02
q2 1 2 q0 12
q2 2 2 q2 22
// assume the '22' we just saw was the one in the
// middle of the input string and that we now need
// to start reading from the stack.
q2 - 2 q3 -
q3 - 2 q4 -
q4 0 0 q4 -
q4 1 1 q4 -
q4 2 2 q4 -
q4 - Z q5 Z
// we read a string in the language and are
// ready to accept in q5. go to dead state q6
// explicitly if still have input.
q5 0 Z q6 Z
q5 1 Z q6 Z
q5 2 Z q6 Z
// consume the rest of the input in the dead state.
q6 0 Z q6 Z
q6 1 Z q6 Z
q6 2 Z q6 Z
的轉換爲q5
和q6
不是嚴格必要的,如果你定義崩潰機器意味着字符串被明確拒絕,這是典型的。我將這些轉換包括在內,以便PDA能夠優雅地使用所有輸入而不會崩潰。
此PDA不確定。這種語言沒有確定性的PDA。基本上,在我們讀取任何子串22
之後,我們必須猜測22
的實例是否是中間的一個。如果是這樣,我們需要開始閱讀最初的字符串,看看我們是否有迴文。如果不是,我們需要繼續推動堆棧上的符號。