純樸的英語的喬姆斯基層次結構

Question

我試圖找到喬姆斯基闡述的正式語法（不受限制，上下文相關，上下文無關，規則）的4個級別的普通（即非正式）解釋。

自從我研究正式語法以來，這個時代已經過去了，現在各種定義讓我想象不清。要清楚，我是而不是正在尋找你能在任何地方找到的正式定義（例如，here和here-我可以和任何其他人一樣）或甚至任何形式的定義。相反，我希望找到的是乾淨而簡單的解釋，爲了完整性而不犧牲清晰度。

Answer 1

如果你還記得產生這些語言的自動機，也許你會更好地理解它。

常規語言由常規自動機生成。他們只具有對過去的有限知識（有計算內存有限制），所以每次你有一個語言後綴取決於前綴（迴文語言），這是不能用常規語言來完成的。

上下文無關語言由非確定性下推自動機生成。他們對過去有一定的瞭解（堆棧，與普通的自動機不同，它不受限制），但堆棧只能從頂層查看，因此您無法完全瞭解過去。

上下文敏感語言由線性綁定的非確定性圖靈機生成。他們知道過去，可以處理不同的情況，因爲他們是非確定性的，並且可以隨時訪問所有過去。

無限制的語言由圖靈機生成。根據Church-Turing-Thesis圖靈機能夠計算出你能想象得到的一切（這意味着一切都是可以確定的）。

Answer 2

對於常規語言，有許多等同的特徵。他們提供了很多不同的方式來查看正規語言。很難給出一個「簡單英語」的定義，如果你很難理解任何常規語言的特徵，那麼「簡單英語」的解釋不太可能會有所幫助。從定義和各種閉包屬性中要注意的一點是，正規語言以某種方式體現了「有限性」的概念。但是，如果不熟悉常規語言，這又難以理解。

你是否發現有限自動機的概念不簡單和乾淨？

讓我提一些許多等價刻畫的（至少對其他讀者）：

• 語言由所接受alternating finite automata
• 語言接受nondeterministic finite automata
• 語言接受deterministic finite automata
• 語言接受通過two-way deterministic finite automata
• 由left-linear grammars產生的語言
• 語言right-linear grammars
• 語言regular expressions生成的語言。
• right-congruence of finite index的某些等價類的聯合。
• 有限索引同餘的某些等價類的聯合。
• 在有限幺半羣的子集的幺半羣同態下的逆映像。
• 語言可以單字二階邏輯在單詞中表示。

Answer 3

常規：這些語言回答是/否與有限自動機

上下文無關：這些語言給定的輸入字（使用狀態machiene和堆棧）時，我們總是可以回答是/否如果是語言的構件

上下文敏感：只要生產語法永遠不會收縮（α - >β），我們可以肯定的回答/無（使用狀態machiene和的存儲器塊，它是線性的與輸入大小）

遞歸ennumerable：它可以回答是，但在任何情況下，它會進入無限循環

看到this視頻完整的解釋。