如何將CFG轉換爲圖靈機

Question

如何將CFG轉換爲TM？我有一個關於如何將DFA轉換爲TM的基本思路，但我想不出一種恰當的做法。

我可以得到一些關於此的一般實施步驟嗎？

Answer 1

1. 使用標準算法構建下推自動機（PDA）。我不會詳細討論任何特定的構造（單獨的問題將會是一個更好的地方）但您可以搜索「convert cfg to pda」並獲得結果。一個例子是here。

2. 從PDA構建兩帶圖靈機如下：

   • 圖靈機讀取輸入膠帶（膠帶＃1）左到右
   • 圖靈機使用的第二帶作爲堆棧，在推動時向右移動，在彈出時向左移動。

3. 使用標準結構從雙帶機器構造一個香草單帶圖靈機。單磁帶和雙磁帶TM的等價證據是一個建設性的證明，您可以按照隱含的算法爲您的CFG語言顯示構建一個單磁帶TM。

Answer 2

CFG的每個生成的單詞都可以寫成一個分析樹。如果你得到了由CFG生成的字符串，這些就是你的分析樹的葉子。要確定字符串是否由CFG生成，您只需從葉子到內部節點直到根節點。所以總的想法是扭轉生產規則。如果你可以到達根目錄，那麼字符串就是語法的一部分。如果你在某一點上，沒有轉向生產規則，那麼這個詞不是由CFG生成的。請注意，如果有多種可能性，您需要嘗試所有可能性，如果有可能，則該字符串由CFG生成。如果沒有任何作品，它不是。