grammar - チョムスキー言語タイプ

Question

私は4つの異なるチョムスキー言語タイプを理解しようとしていますが、私が見つけた定義は私にとって実際には何の意味もありません。タイプ0は自由文法、タイプ1は文脈依存、タイプ2は文脈自由、タイプ3は通常です。それで、誰かがこれを説明して、それを文脈に入れてくれませんか、ありがとう。

Answer 1

言語は、その言語に属する単語のセットです。ただし、多くの場合、言語内のすべての単語を一覧表示する代わりに、問題の言語を識別するために、言語の単語（およびそれらのみ）を生成する一連のルールを指定するだけで十分です。

注：同じ言語をdesrcibeするルールのセットが複数存在する可能性があります。

一般に、ルールに課せられる制限が多いほど、言語の表現力は低下しますが（ルールから生成できる単語は少なくなります）、単語がルールで指定されている言語に属しているかどうかを認識しやすくなります。後者のため、同じ言語を生成できるように、ルールに最も制限のある言語を特定したいと思います。

ルールについて一言：一般的に、あなたは4つの項目（別名4タプル）を持つ形式言語を記述します：

1. 非終端記号のセット（N）
2. 終端記号のセット（T）
3. 一連のプロダクションルール（P）
4. 開始記号（S）

終端記号（別名文字）は、言語の単語が構成する記号であり、通常は小文字の英語の文字のサブセットです（例：'a'、'b'、'c'）

非終端記号は、単語の生成における中間状態を示しており、可能な変換がまだ中間の「単語」に適用できることを示しています。終端記号と非終端記号の間に重複はありません（つまり、2つのセットの共通部分は空です）。非終端記号に使用される記号は、通常、大文字の英字のサブセットです（たとえば、「A」、「B」、「C」）。

ルールは、一連の終端記号と非終端記号で可能な変換を示します。それらは次の形式になっています：左側->右側。左側と右側の両方が一連の終端記号と非終端記号で構成されています。ルールの例：aBc-> cBa。これは、単語の生成中に一連の記号「aBc」（中間の「単語」の一部として）を一連の「cBa」に置き換えることができることを意味します。

開始記号は、単語生成の「ルート」または「開始」を示す専用の非終端記号（通常はSで示されます）です。つまり、一連の単語生成で適用される最初の規則には、常に開始記号があります。その左側として。

すべての非終端記号が終端記号に置き換えられると、単語の生成は正常に終了します（したがって、最後の「中間単語」は終端記号のみで構成され、問題の言語の単語に到達したことを示します）。

すべての非終端記号が終端記号に置き換えられていない場合、単語の生成は失敗しますが、現在の中間の「単語」に適用できる生成規則はありません。この場合、世代は、プロダクションルールアプリケーションの異なるパスに従って、開始シンボルから新たにストラットする必要があります。

例：

L = { T、N、P、S}、

どこ

T = {a、b、c}

N = {A、B、C、S}

P = {S-> A、S-> AB、S-> BC、A-> a、B-> bb、C-> ccc}

これは、「a」、「abb」、「bbccc」の3つの単語の言語を示します。

ルールの適用例：

S-> AB-> aB-> abb

ここで、1）開始記号（S）から開始し、2）2番目のルールを適用し（SをABに置き換え）、3）4番目のルールを適用し（Aをaに置き換え）、4）5番目のルールを適用しました（Bをbbに置き換えます） ）。結果の「abb」には非終端記号がないため、これは言語の単語です。

ルールについて一般的に話すとき、ギリシャ語の記号alpha、beta、gammaなどは、（潜在的に空の）一連の終端記号+非終端記号を示します。ギリシャ文字のイプシロンは、空の文字列（つまり、空の一連の記号）を示します。

チョムスキー階層の4つの異なるタイプは、異なる表現力（ルールに対する異なる制限）の文法を記述します。

• タイプ0（または無制限）文法によって生成された言語は、最も表現力があります（制限が少ない）。帰納的可算言語のセットには、チューリングマシン（基本的にはコンピューター）を使用して生成できる言語が含まれています。つまり、このタイプよりも表現力のある言語（英語など）を使用している場合、その言語のすべての（そしてこれらの単語のみ）をリストできるアルゴリズムを作成することはできません。ルールには1つの制限があります。ルールの左側を空にすることはできません（「突然」シンボルを導入することはできません）。

• タイプ1（状況依存）文法によって生成される言語は、状況依存言語です。ルールには、次の形式であるという制限があります。アルファAベータ->アルファガンマベータ。ここで、アルファとベータは空であり、ガンマは空ではありません（例外：S->イプシロンルール。これは次の場合にのみ許可されます。開始記号Sは、どのルールの右側にも表示されません）。これにより、ルールの左側に少なくとも1つの非終端記号が含まれるように制限され、「コンテキスト」を持つことができます。このルールの例の非終端記号Aは、ガンマに置き換えることができます。、アルファとベータに囲まれている（「コンテキスト内にある」）場合のみ。ルールを適用すると、コンテキストが保持されます（つまり、アルファ版とベータ版は変更されません）。

• タイプ2（文脈自由）文法によって生成される言語は、文脈自由言語です。ルールには、A-> gammaの形式であるという制限があります。これにより、ルールの左側に非終端記号が1つだけあり、「コンテキスト」がないように制限されます。これは基本的に、中間語に非終端記号が表示されている場合、その非終端記号が左側にあるルールのいずれかを適用して、周囲に関係なく右側に置き換えることができることを意味します。非終端記号の。ほとんどのプログラミング言語には、文脈自由生成の文法があります。

• タイプ3（正規）文法によって生成される言語は正規言語です。ルールには、A->aまたはA->aBの形式であるという制限があります（ルールS->イプシロンは、開始記号Sがルールの右側に表示されない場合に許可されます）。各非終端記号は、正確に1つの終端記号（および場合によっては1つの非終端記号も）を生成する必要があります。正規表現は、このタイプの言語を生成/認識します。

これらの制限のいくつかは、変更された文法が同じ表現力を持つように維持する方法で解除/変更することができます。変更されたルールにより、他のアルゴリズムが言語の単語を認識できるようになります。

（前述のように）言語は多くの場合、複数の文法（異なるタイプに属する文法でも）によって生成される可能性があることに注意してください。語族の表現力は通常、それらの言語を生成できる最も制限の厳しい文法のタイプの表現力と同等です（たとえば、通常の（タイプ3）文法によって生成される言語は、タイプ2の文法によっても生成できますが、その表現力はパワーはまだタイプ3の文法のパワーです）。

例

正規文法

T = {a、b}

N = {A、B、S}

P = {S-> aA、A-> aA、A-> aB、B-> bB、B-> b}

ゼロ以外の数の「a」で始まり、その後にゼロ以外の数の「b」が続く単語を含む言語を生成します。各単語がいくつかの「a」とそれに続く同数の「b」で構成され、正規文法を使用する言語を説明することはできないことに注意してください。

文脈自由文法

T = {a、b}

N = {A、B、S}

P = {S-> ASB、A-> a、B-> b}

ゼロ以外の数の「a」で始まり、その後に同数の「b」が続く単語を含む言語を生成します。各単語が多数の「a」、同数の「b」、同数の「c」で構成され、文脈自由文法を使用する言語を説明することはできないことに注意してください。

状況依存文法

T = {a、b、c}

N = {A、B、C、H、S}

P = {S-> aBC、S-> aSBC、CB-> HB、HB-> HC、HC-> BC、aB-> ab、bB-> bb、bC-> bc、cC-> cc}

ゼロ以外の数の「a」で始まり、同じ数の「b」、同じ数の「c」が続く単語を含む言語を生成します。この文法でのHの役割は、CBの組み合わせをBCの組み合わせに「交換」できるようにすることです。これにより、Bを左側に、Cを右側に集めることができます。単語が一連の「a」で構成され、「a」の数が状況依存文法の素数である言語を記述することはできませんが、その言語を生成する無制限文法を書くことは可能であることに注意してください。