如何獲得PDA的轉換關係？

Question

我知道如何弄清楚開始狀態，接受狀態，輸入字母和所有東西。但你如何發展PDA的過渡關係？對於FSM，（q0，a），q1）表示如果從q0開始並得到a，則轉換到q1。但是（S，a，e），（S，a）是什麼意思？ （S是開始狀態，e是epsilon）

Answer 1

而不是（S，a，e），（S，a）中應該是底部符號（看起來像顛倒的T）的ε。稍後我會解釋這一點。

第一個S就是你現在所處的狀態。這對應於FSM中的q0。

a是您閱讀的符號，與FSM中的a相同。請注意，當你得到一個和而不是一個這意味着你是在你的字符串的末尾，沒有什麼可讀的。

主要區別在於下一個字母，在這種情況下是e。這表示當您閱讀a時位於堆棧頂部的單個堆棧符號。從技術上講，你永遠不會讀空棧。在計算機中，這與讀取空內存相同，但它不能完成。這是因爲堆棧的「底部」包含一個表示您位於底部的符號。傳統上，這是使用顛倒的T（底部符號）表示的。

第二個括號中的S表示您將要進入的狀態，就像FSM中的q1一樣。

最後，第二個括號中的a是要添加到堆棧上的符號（或符號）。每當你從棧中讀取某些東西（每次發生轉換時），該符號都會從堆棧中移除。然後，你可以把一個新的符號或幾個新的符號放到堆棧上，或者你可以不加任何東西（e）。當你剛剛閱讀底部符號時，什麼都不說，意味着你已經完成了，並且你接受了字符串（如果接受空棧）。你也可以通過最終狀態來接受，但空的堆棧更簡單一些。

我會告訴你一個簡單的例子，PDA {a^n b^n | n> = 0}。我們的字母顯然是{a，b}，我們需要2個狀態（一個用於a部分，另一個用於b部分），我們稱它們爲{p，q}。我們會讓p成爲我們的開始狀態。我們的堆棧字母表，我們可以放到堆棧上的符號是{bottom，A}。 Bottom總是堆棧字母表的一部分，每當我們得到一個a（並且每當我們得到一個b時彈出一個），我們會將A推入堆棧。讓我們接受空堆棧，這意味着當我們讀取e作爲符號，底部作爲堆棧符號時，如果我們不將任何東西放回堆棧，那麼我們已經接受了該字符串。我們三角洲過渡如下：

(p,e,bottom),(p,e) //this is an accepting state for a^0 b^0 
(p,a,bottom),(p,A bottom) //we read an a and we're at the bottom of the stack, we add an A to the stack and put back the bottom symbol below it. 
(p,a,A),(p,AA) //we read an A off the stack and an *a* in our string, we put back the A we read from the stack and add another one 
(p,b,A),(q,e) //we read an A off the stack and a *b*, so we go to our state q, and don't add anything to the stack. 
(q,b,A),(q,e) //every time we get a *b* and there's an A on the stack, remove it 
(q,e,bottom),(q,e) //this is an accepting state, as we've canceled out all the a's with b's and we're done reading our string. 

注意，有過渡不允許的，如之前的任何一個的得到一個b。通過不包括它們，需要它們的字符串不被接受。希望這可以幫助！