如何設計一個下推自動機

Question

我將如何設計一個PDA，接受平衡括號和括號，例如 （[] []），我很難開始。我需要幫助編寫這個問題的轉換函數。任何幫助表示讚賞

Answer 1

我通常不會爲他們做別人的整個作業，但現實情況是，當涉及到自動機，即使我做什麼，除非你真的這麼做，否則你將無法幫到你瞭解這些事情是如何運作的，可悲的事實是，大多數學校並沒有很好地教他們開始。

讓我們想想如何PDA工作而忘記了狀態和轉換和諸如此類的東西現在：當我們的PDA獲取輸入它應該像這樣工作：

• 如果沒有輸入：
  • 如果堆棧的頂部是空的（這通常用一些特殊的值來表示，例如$），那麼我們的PDA接受字符串：它是一個正確平衡的括號和括號。
  • 否則我們進入錯誤狀態。該字符串不是一個正確平衡的括號和括號字符串。
• 如果輸入是(或[，則將輸入壓入堆棧並查看下一個輸入字符。
• 如果輸入的是)則：
  • 如果堆棧的頂部是一個(彈出堆棧的頂部，並期待在接下來的輸入。
  • 否則，進入錯誤狀態。該字符串不是一個正確平衡的括號和括號字符串。
• 如果輸入的是]則：
  • 如果堆棧的頂部是一個[彈出狀態的頂部，並期待在接下來的輸入。
  • 否則，進入錯誤狀態。該字符串不是一個正確平衡的括號和括號字符串。現在

，知道我們的PDA所要做的，讓我們去想想如何更正式地描述我們的PDA。我們將假設：

• Τhe組有效輸入碼元的Σ= {(，)，[和]}
• 初始堆棧符號Z = $
• Τhe組有效堆棧符號Γ= { (，[}∪ž
• 的狀態集合Q = {Q0，ACCEPT的，REJECT}
• 初始狀態Q0。

使用類似於上http://en.wikipedia.org/wiki/Pushdown_automaton因爲我們可以思考的狀態和事情如何流動PDA狀態轉換描述的符號：

• （Q0，ε，頂部= $，接受無）這告訴我們的PDA：當你處於狀態q0並且沒有更多的輸入並且堆棧頂部是$時，轉到ACCEPT狀態，保持堆棧不變。

• （Q0，ε，頂部= (，拒絕無）這告訴我們的PDA：當你在狀態Q0，並沒有更多的輸入和堆棧的頂部是一個(去拒絕狀態，保持堆棧不變。

• （Q0，ε，頂部= [，拒絕無）這告訴我們的PDA：當你在狀態Q0，並沒有更多的輸入和堆棧的頂部是一個[去拒絕狀態，保持堆棧不變。

• （Q0，(，頂部=頂部，Q0，推動(）這告訴我們的PDA：當你在狀態Q0和輸入是(那麼，不管是什麼在堆棧的頂部，轉到狀態q0並將(推入堆棧。

• （Q0，[，頂部=頂部，Q0，推動[）這告訴我們的PDA：當你在狀態Q0和輸入是[那麼，不管是什麼在堆棧的頂部，轉到狀態q0並將[推入堆棧。

• （Q0，)，頂部= (，Q0，流行）這告訴我們的PDA：當你在狀態Q0和輸入是)和堆棧的頂部是一個(然後去狀態q0，並關閉堆棧頂部。

• （Q0，)，頂部= [，拒絕無）這告訴我們的PDA：當你在狀態Q0和輸入是)和堆棧的頂部是一個[然後去拒絕堆棧，保持堆棧不變。

• （Q0，)，頂部= $，拒絕無）這告訴我們的PDA：當你在狀態Q0和輸入是)和堆棧的頂部是一個$然後去拒絕堆棧，保持堆棧不變。

• （Q0，]，頂部= [，Q0，流行）這告訴我們的PDA：當你在狀態Q0和輸入爲]，堆棧的頂部是一個[然後去狀態q0，並關閉堆棧頂部。

• （Q0，]，頂部= (，拒絕無）這告訴我們的PDA：當你在狀態Q0和輸入爲]，堆棧的頂部是一個(然後去拒絕堆棧，保持堆棧不變。

• （Q0，]，頂部= $，拒絕無）這告訴我們的PDA：當你在狀態Q0和輸入爲]，堆棧的頂部是一個$然後去拒絕堆棧，保持堆棧不變。

我們可以使用更多狀態來實現這一點，但有趣的是要注意一個「處理」狀態就足夠了。

您可能還想指出，取決於您的教師，您可能不需要明確添加REJECT狀態，儘管這樣做很好。

我希望這會有所幫助。

Answer 2

這可能會幫助你開始：

bool check_and_pop(char c) { 
    if (top() == c) { 
    pop(); 
    return true; 
    } 
    return false; 
} 

int check_input() { 
char c; 
while ((c = getc())) { 
    switch (c) { 
    case '(': case '{': case '[': push(c); break; 
    case ')': 
     if (!check_and_pop('(') 
     return REJECT; 
     break; 
    case '}': 
     if (!check_and_pop('{') 
     return REJECT; 
     break; 
    // ... 
} 
// end of input, check the stack to accept/reject 
if (stack_size() == 0) 
    return ACCEPT; 
else 
    return REJECT; 
}