爲以下語言創建下推自動機

Question

所以我在練習中遇到了問題，我發現了這個問題。 構造一個接受西格瑪語言L的npda（a，b，c）。

L = {瓦特：A = B + 1的數目的數目}

所以我，因爲它接受具有一個以上的，則字母B的所有字符串解釋它。我相信所有的國家都應該有一個循環（c，landa，landa），因爲我們並不關心c。在此之後，我感到非常困惑，因爲有很多案例可以報道，因爲a和b的位置是任意的。解決這個問題的方法是什麼？謝謝！！

Answer 1

PDA可以使用堆棧來記住任意數量的信息。這使得PDA比有限自動機更有能力。確定PDA的關鍵是弄清楚如何使用這個堆棧，然後圍繞這個堆棧建立一個PDA。

我們如何使用堆棧來確保a s的數量等於b s的數量，再加上一個？那麼，堆棧可以很容易地跟蹤已經看到的符號的運行平衡。例如，如果我們看到四個a和兩個b s，我們的堆棧可能通過包含aaZ來代表這個事實，其中Z是「堆棧底部」符號。當然，我們還可以使用其他方法和其他表示法，但對於這類問題來說，這是一個非常整齊的方法。爲了完全解釋該表示：

1. 堆棧最初是Z，只是堆棧符號的底部。
2. 如果我們看到一個a和堆棧的頂部是a或Z，我們添加另一個a。
3. 如果我們看到一個a，堆棧頂部是b，我們刪除一個b。
4. 如果我們看到一個b，堆棧頂部是b或Z，我們再添加一個b。
5. 如果我們看到一個b，堆棧頂部是a，我們刪除一個a。
6. 如果我們看到c，請單獨保留堆棧。

如果我們對所有的輸入做了一遍又一遍，然後將堆棧的內容將等於x^m，其中x是取其a和b更頻繁地發生，並且m是絕對值每個符號的數量的差異。

要接受您的語言，您必須簡單地識別輸入耗盡且堆棧組合等於aZ的情況。這可以通過添加一些狀態和lambda/epsilon轉換來清除堆棧和/或進入接受狀態來完成。

感謝Peter Leupold指出原始答案的其餘部分的語法錯誤。我試圖解決這個問題，並且不知道答案得到了多長時間，所以我忽略了這一點。我會簡單地補充說另一種可能性是爲一種語言生成一個CFG，並使用一種算法爲其派生PDA。在這種情況下，對我來說，直接給PDA是不那麼羅嗦的。