Automata-theory-chomsky-classification-of-grammars
提供：Dev Guides
文法のチョムスキー分類
Noam Chomoskyによると、4つのタイプの文法があります-タイプ0、タイプ1、タイプ2、およびタイプ3。 次の表は、それらが互いにどのように異なるかを示しています-
| Grammar Type | Grammar Accepted | Language Accepted | Automaton |
|---|---|---|---|
| Type 0 | Unrestricted grammar | Recursively enumerable language | Turing Machine |
| Type 1 | Context-sensitive grammar | Context-sensitive language | Linear-bounded automaton |
| Type 2 | Context-free grammar | Context-free language | Pushdown automaton |
| Type 3 | Regular grammar | Regular language | Finite state automaton |
次の図をご覧ください。 それは文法の各タイプの範囲を示しています-
タイプ-3文法
- Type-3文法*は通常の言語を生成します。 タイプ3文法には、左側に単一の非終端記号があり、右側に単一の終端記号または単一の非終端記号が続く単一の終端記号が必要です。
プロダクションは、 X→aまたはX→aY の形式である必要があります
ここで、 X、Y∈N （非終端）
および a∈T （端末）
*S* がルールの右側に表示されない場合、ルール* S→ε*が許可されます。例
X → ε
X → a | aY
Y → bタイプ-2文法
- Type-2文法*は、文脈自由言語を生成します。
作品は* A→γ*の形式でなければなりません
ここで、 A∈N （非終端）
および*γ∈（T∪N）**（端末および非端末の文字列）。
これらの文法によって生成されたこれらの言語は、非決定的プッシュダウンオートマトンによって認識されます。
例
S → X a
X → a
X → aX
X → abc
X → εタイプ-1文法
- Type-1文法*は、状況依存言語を生成します。 作品は次の形式である必要があります
αAβ→αγβ
ここで、 A∈N （非終端）
および*α、β、γ∈（T∪N）**（端末および非端末の文字列）
文字列*α*および*β*は空でもかまいませんが、*γ*は空でない必要があります。
Sがルールの右側に表示されない場合、ルール* S→ε*が許可されます。 これらの文法によって生成された言語は、線形有界オートマトンによって認識されます。
例
AB → AbBc
A → bcA
B → bタイプ-0文法
- Type-0文法*は、再帰的に列挙可能な言語を生成します。 プロダクションには制限がありません。 それらは、すべての正式な文法を含む任意のフェーズ構造文法です。
チューリングマシンによって認識される言語を生成します。
生成は、*α→β*の形式にすることができます。ここで、*α*は、少なくとも1つの非端末を持つ端末と非端末の文字列であり、*α*をヌルにすることはできません。 *β*は、端末と非端末の文字列です。
例
S → ACaB
Bc → acB
CB → DB
aD → Db
