DFA到PDA的轉換

Question

我正在尋找算法將確定性有限自動機轉換爲按下自動機。

任何幫助表示讚賞。

謝謝！

Answer 1

的wikipedia article說

下推自動從有限 狀態機有兩點不同：

1. 他們可以使用堆棧的頂部，以決定哪些過渡到 服食。
2. 他們可以操作堆棧作爲執行轉換的一部分。

下推自動選擇由輸入信號， 當前狀態，並且在頂部 堆疊的符號索引的表的過渡 。這意味着 這三個參數完全確定 選擇的轉換路徑爲 。有限狀態機只需 看看輸入信號和 目前的狀態：他們沒有任何堆棧可以與 一起工作。下推自動機添加 堆棧作爲參數供您選擇。

...
下推自動機相當於 上下文無關文法：每 上下文無關文法，存在 下推自動機，使得由語法產生的 語言是 相同與所產生的語言 由自動機，這很容易 證明。的情況正好相反，雖然 更難證明：每下推自動機 存在一個上下文 語法，使得由自動機所產生的語言 是 與語言相同由語法產生的 。

Answer 2

DFA的PDA版本看起來是一樣的，除了每個狀態轉換也不會在堆棧上壓入任何東西，並且不會彈出堆棧。

Answer 3

由於PDA是DFA的擴展，只有一個附加功能：堆棧。 由於PDA的轉換是由三元組（當前狀態，輸入，堆棧頂部的元素）決定的，而DFA的轉換由元組（當前狀態，輸入）確定。唯一的區別是堆棧頂部的元素。您可以通過在堆棧

的頂部轉化插入作爲元素的元組三，e（空字符串）和更改後的狀態DFA的所有過渡轉換，推動e（空字符串）堆棧。

Answer 4

我回答這個老問題，以防別人看着它。

只需添加一個堆棧即可輕鬆實現DFA到PDA的轉換。但是可能會對DFA的語義進行更改，並且在您以手動方式更改該方法後，可能會以較少的狀態結束於PDA。我最近面臨這個問題。它有點像這樣，

在一個系統（不是編譯器或類似的東西）中，之前編寫的代碼是由於某些原因使用DFA編寫的。轉換髮生在用戶使用各種功能通過代碼進行時。經過一段時間後，一組新的過渡功能到達，可以按任何順序使用。並且這些新功能中的任何一個之後的狀態可以通過這些功能之一改回到之前的狀態。使用FST解決這個問題的唯一方法是添加大量的新狀態來支持這種行爲，這是我的一大筆工作。但是，我只是從DFA更改爲PDA。堆棧非常好地跟蹤轉換，問題可以通過少得多的狀態來解決。實際上，我只需要添加N個狀態，其中N是到達的新功能的數量。

我不知道是否有人可以輕鬆自動化這種過程。但是，你去了，以防萬一有人好奇它。