如何去構建特定語言的圖靈機？

到目前爲止，我遇到了兩種類型的語言。有嚴格格式的語言，如如何去構建特定語言的圖靈機？

L = {a^n b^n c^n | N> = 1}

這種語言很嚴格的，例如一個公司將收到B的等

的其他類型的我遇到經常來是語言它可以是任何順序。

L = {A，B} *，其中a的數> B的

這種語言的數目可以是一個和b的其不是卡在適當位置的任何順序。

For the languages that are structured this machine conveys the general idea

但我無法找到的機器在那裏它可以是任何字符的順序模式。

例如

L = {A，B，C} * | a's等於b和c的最小值。

這些語言的模式是什麼？以及什麼是一些真正有用的技術來設計這些？

來源

2017-06-29 EaEaEa

由於類似的原因存在停機問題，沒有通用的方法來解決所有問題。如果有，你可以通過在爲找出一個給定的機器是否停止對一個給定的輸入機器的要求，一般的做法會導致機器H，這是不可能的。圖靈機規範是軟件，沒有解決所有問題的編寫軟件的通用解決方案，同樣也沒有指定圖靈機的通用解決方案。你必須考慮問題並自行提出解決方案。 – Welbog

我知道，但對於上面的例子，似乎有一個通用結構。只適用於這些類型的語言。你可能有任何想法如何去創建TM的一些技術？比如寫出接受/拒絕的字符串。等等。 – EaEaEa

我會用類似的方式來處理它，試圖用傳統的編程語言來處理它：將零件細分爲可管理的零件。比如一個指定一個特定角色的作品，一個發現兩個數字最小的作品和一個以正確順序調用其他作品的作品。 – Welbog

#a> #b的例子是上下文無關語言的典型例子，它被下推自動機識別。這些設備只能沿着輸入移動一次，並有一個下推式存儲（堆棧）。基本的想法是爲輸入中的每一個讀入一個堆棧，對於b你刪除一個。找到一種方法來處理前綴比你更多的b。然後你完全接受在讀完整個輸入之後你是否有剩下的東西。

如果允許使用輔助磁帶，這很容易在圖靈機上實現。只需使用一個作爲堆棧。如果您的最後一個示例涉及更多數字，請使用更多輔助磁帶。

如果你沒有輔助磁帶，你必須更多的使用讀寫頭。例如，使用一個結構：

input%stack1%stack2%stack3%

其中％是一個不會在其他地方出現的分隔符號。另一種選擇是不屬於下推自動機的方法：標記符號。例如，對於#A> #B：

標記第一個未標記b
標記第一個未標記一個
如果有未標記b左，轉到1 .;否則檢查是否至少有一個未標記的左邊 - 如果接受，否則拒絕

這些是可以用於這些計數問題的兩種標準技術。當然，正如人們已經評論過的那樣，對於每種給定的語言，您都必須調整您的解決方案。

來源

2017-06-30 09:50:45

如何去構建特定語言的圖靈機？

回答

相關問題