如何將cfg轉換爲具有2個狀態的pda？

我遇到了一些問題，我在計算機科學理論研究...如何將cfg轉換爲具有2個狀態的pda？

任何人可以解釋我的算法，我們如何可以將上下文無關語法（cfg）轉換爲相應的下推自動機（pda ）只有2個狀態？

2017-05-08 shahin gh

這個問題會更好地指向[cs.se]，但它會作爲重複被關閉。請參閱https://cs.stackexchange.com/questions/19946/how-to-get-2-state-pda-for-cfg或此搜索：https://cs.stackexchange.com/search?q= convert + CFG + to + PDA – rici

我發現他們之前，但他們沒有清楚地回答@ rici –

狀態1：不接受。通過空轉換到自身將S推入空棧。 G中的每個產品都會自動轉換爲自我，但會將生成的字符串向後推送到堆棧中。在讀取終端符號x時將空轉換爲自身，x在堆棧頂部。在空堆棧上空轉換到狀態2。

狀態2：接受沒有更多輸入和空堆棧。

操作理論：堆棧用於在語法語言中派生字符串，方法是向後寫出，然後在讀取輸入時彈出它們。如果用完輸入且堆棧爲空，則可以進入狀態2並接受。

來源

2017-05-09 21:00:40 Patrick87

如何將cfg轉換爲具有2個狀態的pda？

回答

相關問題