文法の制約なし

オートマトン理論において、非制限文法（セミ・チュー文法、タイプ0文法、または句構造文法とも呼ばれる）のクラスは、チョムスキー階層で最も一般的な文法クラスである。非制限文法の生成には、それぞれの左辺が空でないという点以外に制限はない。^{[ 1 ]： 220}この文法クラスは、任意の再帰的に列挙可能な言語を生成できる。

制約のない文法は形式文法である${\textstyle G=(N,T,P,S)}$、 どこ

• ${\displaystyle N}$は非終端記号の有限集合である。
• ${\displaystyle T}$は、有限個の終端記号の集合であり、${\displaystyle N}$そして${\displaystyle T}$互いに素、^{[注1 ]}
• ${\displaystyle P}$は、次の形式の有限個の生成規則の集合である。${\displaystyle \alpha \to \beta ,}$どこ${\displaystyle \alpha }$そして${\displaystyle \beta }$は記号の文字列です${\displaystyle N\cup T}$そして${\displaystyle \alpha }$は空文字列ではなく、

• ${\displaystyle S\in N}$は特別に指定されたスタートシンボルです。^{[ 1 ]： 220}

その名前が示すように、無制限文法が持つことができる生成規則の種類には、実際には何の制限もありません。^{[注2 ]}

非制限文法は再帰的に列挙可能な言語を特徴づける。これは、すべての非制限文法について、${\displaystyle G}$認識可能なチューリングマシンが存在する${\displaystyle L(G)}$そしてその逆もまた然り。制約のない文法が与えられた場合、そのようなチューリングマシンは、2テープ非決定性チューリングマシンとして簡単に構築できる。^{[ 1 ]： 221} 最初のテープには入力語が含まれる。${\displaystyle w}$テスト対象であり、2番目のテープは機械が文形式を生成するために使用する。${\displaystyle G}$チューリングマシンは次に以下の処理を行います。

1. 2番目のテープの左端から開始し、繰り返し右へ移動するか、テープ上の現在の位置を選択してください。
2. 非決定論的に生産を選択する${\displaystyle \beta \to \gamma }$の作品から${\displaystyle G}$。
3. もし${\displaystyle \beta }$2番目のテープ上のどこかの位置に現れるので、${\displaystyle \beta }$による${\displaystyle \gamma }$その時点で、テープ上のシンボルを相対的な長さに応じて左右にシフトする可能性がある${\displaystyle \beta }$そして${\displaystyle \gamma }$（例：${\displaystyle \beta }$より長い${\displaystyle \gamma }$（テープ記号を左にシフトします）。
4. テープ2に記録された文形式をテープ1の単語と比較します。一致すれば、チューリングマシンはその単語を受け入れます。一致しない場合は、チューリングマシンはステップ1に戻ります。

このチューリングマシンが、文形式をすべて生成し、かつその文形式のみを生成することは容易にわかる。${\displaystyle G}$最後のステップが任意の回数実行された後、2番目のテープ上で言語が実行されます。${\displaystyle L(G)}$再帰的に列挙可能でなければならない。

逆の構成も可能です。あるチューリングマシンが与えられた場合、左辺に 1 つ以上の非終端記号を持つ生成規則のみを使用する同等の無制限文法^{[ 1 ] : 222}を作成できます。したがって、任意の無制限文法は、チューリングマシンに変換して元に戻すことで、常に後者の形式に従うように同等に変換できます。一部の著者は、後者の形式を無制限文法の定義として使用しています。

与えられた文字列が${\displaystyle s}$与えられた無制限文法によって生成できるかどうかという問題は、その文法と同等のチューリングマシンによって受理されるかどうかという問題と同等である。後者の問題は停止問題と呼ばれ、決定不能である。

再帰的に列挙可能な言語は、クリーネスター、連結、和集合、積集合に関しては閉じていますが、差集合に関しては閉じていません。再帰的に列挙可能な言語#閉包特性を参照してください。

制約のない文法がチューリングマシンと等価であるということは、普遍的な制約のない文法、つまり、言語の説明が与えられれば他のあらゆる制約のない文法の言語を受け入れることができる文法が存在することを意味する。このため、理論的には制約のない文法に基づいてプログラミング言語を構築することが可能である（例えば、Thue）。

• ラムダ計算
• セミ・テュー方式– 終端記号と非終端記号を区別せず、左辺が空でも許容する。