掌上電腦接受哪些語言

Question

我很努力地理解在推送和彈出堆棧上和下的項目時下推自動機的符號。

我知道堆棧必須是空的才能接受字符串。

這裏是我的PDA：

如果我創建一個轉移圖說輸入0011，我會做這樣的：

State   Input   Stack 

q0    0011   ɛ 

q0    011   0 

q0    11   00 

q0    1    100 

q0    ɛ    1100 

由於輸入是空的，堆棧不是空的，這是不被接受的？

所以，如果我把輸入像那樣的事情...我敢肯定，這是錯誤的，因爲如果我把任何字符串放入PDA它不會接受。我想總結一下我的實際問題，第一個非終結符號（0，ɛ/ 0）（1，ɛ\ 1）的符號表示這是否意味着在輸入0下向堆棧中添加0（相同對於輸入1，做相反的事情）？

對於第二個終端，它是否意味着......這是什麼讓我感到困惑（我是否將字符串從堆棧或輸入中移出？）我想我必須從堆棧中移除項目？

那麼這是否意味着此PDA所接受的語言是空集？如果不是，你能解釋我哪裏出錯了嗎？

Answer 1

有不同的約定，但一個共同的約定是，當您接受：

1. 輸入信息已耗盡;和
2. 你是一個接受狀態;和
3. 堆棧爲空。

真的，你可以使用這些規則的幾個子集，並使用其他規則集，並獲得也適用於上下文無關語言的系統。機器在這些系統中會有不同的解釋，但表達能力是相同的。

假設上述三點系統，正如Welbog指出的那樣，該PDA接受字母表{0, 1}上的均勻長度迴文的語言。我們來談談每個州的情況。

1. q0只要再次只要你想讀或者0或1分別推0或1，壓入堆棧，一遍又一遍。如果您閱讀字符串x，則將字符串x推入堆棧。

2. q1讀取或者0或1，如果你對堆棧的頂部是符號，彈出它關閉，過去，只要你想對獲得。如果您閱讀字符串x，您將彈出x^R。

如果我們q1接受狀態，並要求當輸入耗盡堆棧是空的，這意味着：

1. 我們彈出x^R，如果x被讀取，而在狀態q1 。
2. 如果我們在狀態q0中讀取x^R，則堆棧包含x^R。
3. 我們讀x^R然後x和接受，因此我們只接受字符串像x^R x，即偶數長度迴文
4. 此外，任何偶數長度迴文必須通過這個掌上電腦，這導致它的路徑被接受，因爲PDA可以保留q0爲|x|/2輸入符號，轉換爲q1並閱讀剩餘的|x|/2。由於PDA不確定，這足以說明字符串已被接受。