將PDA轉換爲DFA

Question

我期待將PDA轉換爲DFA。 PDA的堆棧永遠不會包含n個以上的符號。

任何幫助將不勝感激。

謝謝

Answer 1

我沒有完整的解決方案，但只是一個想法：對於每一個推一個符號棧S上必須在子圖複製到下一個流行的過渡轉變。新子圖必須接受與PDA中對應子圖相同的子字符串s。當你搜索這樣的轉換時，你必須從內向外進行轉換，這樣子圖中就不會有內部推送和彈出。因此，第一個替換將由兩個轉換組成，並且其他子圖變得越來越大。