下推自動機

Question

我將如何爲0^m 1^n編寫pda，其中| m | > = | n |; 0的數量是否大於或等於1的數量？

我在想：

• 如果你看到一個1或0，將其推到堆棧
• ，如果你看到另一0或者一串0的，將其推到堆棧
• 如果你看到一個1，將其推到堆棧
• ，如果你看到另1後，彈出它從堆棧中

，但是，我不認爲這是正確的。有人可以幫忙嗎？

Answer 1

如果我理解正確的分配，那麼你正在使這種方式變得複雜。 0^m 1^n表示一串0，後面跟着一串1，但在看到1之後沒有0的合法字符串。首先在堆棧上放置一個標記，以便知道它何時爲空（通常＃）。之後，你基本上需要計數0（將它們推入堆棧），並且當你看到堆棧中的1彈出時。輸入完成後，檢查堆棧是否有任何0或您在開始時放入堆棧的符號。

Answer 2

考慮當你有相同數量的0到1的情況。

讓我們從容易開始。你可以從1開始，或者從0開始。這給了我們兩種不同語言的聯合，其中0的數量大於1的數量，反之亦然。

因此，空字符串也是有效的（這給出了第一個狀態將是最終狀態的線索）。

接下來，我們觀察到，我們最終可以有相同數量的0和1的上下。

考慮字符串：

010101或101010.你注意到它總是可以追溯到空棧。這很容易處理。

基本上你有一個PDA，其中啓動開始也是接受狀態。

我不確定你是否知道符號，所以我只是保持簡單的英文。

你有3個狀態，q0，q1，q2。

q0是最終的初始起始狀態。

q0 - > q1有1個轉換1，e - > $（讀取1，爲空棧壓入$符號）。 （如果你讀一個0，彈出一個1），（如果你讀一個1，按一個1）。

還有一個轉換回到起始狀態q0。

q1 - > q0 0，$ - > e（讀取0，堆棧現在爲空）此時，我們有相同數量的0到1。

你這樣做的狀態q2，除了推和彈出0的代替。所以一切都與1和0相反。

然後，你可以非確定性地有任何數量的0，我會留給你。提示：您可以在某處創建1個自我循環來處理此問題。這實際上只需要添加1個狀態即可獲得等於或大於0到1的數字

=====================

因此，在簡單的英語中，您需要考慮兩種情況，首先以1或0開頭。然後，如果你再次得到一個空棧，回到初始/最終狀態，看看你是否再次有1或0。

實施例：

第一閱讀一個1。然後，你讀了0，所以它就像你從頭再來，這一次的字符串：

閱讀0這個時候，讀了1，用從頭再來：

讀取0，讀取0，按下0，讀取1，彈出0，讀取另一個1（堆棧現在爲空），返回初始/最終狀態。

希望有所幫助。