無限制文法

在形式語言理論中，無限制文法是對文法的產生式左右兩側都沒有限制的形式文法。這是喬姆斯基層級中最一般性的文法類，它們可以識別任意的遞歸可枚舉語言。

形式定義

無限制文法是形式文法 $G=(N,\Sigma ,P,S)$ ，這裡的 $N$ 是非終結符的集合， $\Sigma$ 是終結符的集合，這裡的 $N$ 和 $\Sigma$ 是無交集的(實際上這個限制不是必需的，因為無限制文法在非終結符和終結符之間不做真實區分，存在這個指定純粹是為了使得你在嘗試生成文法的句子形式的時候知道何時停止)， $P$ 是形如 $\alpha \to \beta$ 的產生規則的集合，這裡的 $\alpha$ 和 $\beta$ 是在 $N\cup \Sigma$ 中的符號的字符串而 $\alpha$ 是非空字符串， $S\in N$ 是特別指定的開始符號。如名稱所暗含的，在無限制文法可以有什麼類型的產生規則上沒有真實限制。

無限制文法和圖靈機

可以證明無限制文法特徵化了遞歸可枚舉語言。這同於聲稱對於所有無限制文法 $G$ 都存在某個圖靈機有能力識別 $L(G)$ 反之亦然。給定一個無限制文法，這種圖靈機足夠簡單構造為兩磁帶非確定圖靈機。第一個磁帶包含要被測試的輸入字 $w$ ，而機器使用第二個磁帶生成來自 $G$ 的句子形式。圖靈機接着做如下事情:

開始於第二個磁帶的左端並重複的選定要右移或選擇在磁帶上的當前位置。
非確定的從 $G$ 中選定一個產生式 $\beta \to \gamma$ 。
如果 $\beta$ 出現在第二個磁帶的某個位置，在這個點上把 $\beta$ 替代為 $\gamma$ ，依據 $\beta$ 和 $\gamma$ 的相對長度可能要把在磁帶上的符號向左或右移動(就是說如果 $\beta$ 長於 $\gamma$ ，左移磁帶符號)。
比較在磁帶 2 上的結果句子形式和在磁帶 1 上的字。如果匹配，則圖靈機接受這個字。如果不匹配則回到步驟 1。

容易看出這個圖靈機將在最後步驟被執行任意次之後在第二個磁帶上生成 $G$ 的所有的句子形式，所以語言 $L(G)$ 必定是遞歸可枚舉的。

相反構造也是可能的。給定某個圖靈機，有可能建立一個無限制文法。

計算性質

從無限制文法和圖靈機的等價性上，給定一個字符串 $s$ 是否屬於某個無限制文法的語言的決定性問題一般是不可判定的。

給出一個語言的描述完全可能建立一個通用無限制文法有能力接受任何其他無限制文法的語言，如同有可能建立一個通用圖靈機，所以在理論上有可能建造一個基於無限制文法的編程語言。

參見

參考文獻

John Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation 1st edition. Addison-Wesley. 1979. ISBN 0-201-44124-1. (the Cinderella book)