チョムスキー生成文法

簡単な紹介

このテキストは、著者が形式言語および文法の概念を単純で複雑な数学的計算なしで説明しようとした投稿の続きです。 このテキストに対しては非常に多くの回答が寄せられ、著者は自分が続編を書く義務があると考えました。

生成的チョムスキー文法の形式は以下に説明されています。 生成文法を使用して言語を指定する方法は、特にコンピューター言語の機械処理で非常に人気があります。 しかし、通常、翻訳者理論における生成文法の研究は、文脈自由文法で終わります。 後者は、生成チョムスキー文法のかなり狭い特別なクラスであり、通常、パーサーを指定するためのカテゴリ文法（これを行う方法、以下に示します）の形式として使用されます。 後者の状況は、チョムスキーのアプローチの理解を曖昧にするだけです。 次の説明は、このアプローチの構成を理解することに関心がある人を対象としています。

文法定義の生成

文法は、形式言語の究極の記述です。 フォーマル言語は、順番に、有限のアルファベットの文字で構成されるチェーンの任意のセットです。 ここでのセットの意性は、無限、有限、または空になる可能性があるという意味で理解されます。

生成チョムスキー文法の形式は、前世紀の50年代後半にノアムチョムスキーによって導入されました。 短期間で、この形式主義は並外れた人気を獲得しました。 しばらくの間、文法の生成は万能薬と見なされていました-自然言語（つまり、人々が日常のコミュニケーションに使用する言語）を含むあらゆる種類の言語を設定するための普遍的なアプローチ しかし、自然言語を記述するための生成文法はあまり便利ではないことが時間の経過とともに示されています。 現在、生成文法は主に、プログラミング言語やその他のコンピューター言語などの形式言語の構文を記述するために使用されています。

チョムスキーの生成文法は、「生成規則」（プロダクション）のセットとして定義されています。 各ルールはチェーンのペア(w', w'')あり、文法で指定された言語のチェーンを生成するときに、左のチェーンを右のチェーンに置き換えることができます。 このため、ルールは通常w' --> w''として記述され、具体的に何を置き換えることができるかを示します。 文法の規則のセットは空ではなく有限でなければならず、通常はラテンPで示されます。

文法規則のチェーンは、2つのアルファベット（終端文字のアルファベット（終端）と非終端文字のアルファベット（非終端））の文字で構成できます。 終端のアルファベットはTで示されます。このアルファベットは、実際にこの文法が定義する形式言語のアルファベットと一致します。 「ターミナル」という用語の意味は、左側の文法規則では、ターミナル記号のみで構成されるチェーンは存在できないということです。 したがって、そのようなチェーンが置換の結果として判明した場合、チェーンを生成する次のプロセスは停止（終了）します。 非終端記号は、中間チェーンで使用されます。 チェーンを生成するためのアルゴリズムを定義する際の非終端の意味は非常に異なり、通常、このシンボルが使用される文法のタイプに依存します。 非終端記号を使用するさまざまな例について、以下で説明します。

しかし、1つの非終端記号は常に同じ意味を持ちます-それは言語のすべてのチェーンを示します。 この非終端記号は「生成文法の最初の非終端記号」と呼ばれ、通常はラテン語S（開始または文）で示されます。 各生成文法には、左部分が単一の初期非終端記号で構成されるルールが必ず必要です。そうでない場合、この文法では、チェーンを1つでも生成することはできません。

したがって、チョムスキーの生成文法は、4つのG = {N, T, P, S} 。ここで、

• Nは、非終端文字の最後のアルファベットです。
• T終端記号の最後のアルファベット（文法で指定された言語のアルファベットと一致）。
• Pは、生成ルールの有限セットです。
• Sは、文法G最初の非終端記号ですG

生成文法言語

チョムスキーの生成文法は、生成規則に基づいて、文法の最初の非終端からの連鎖の有限数の順列によって言語を定義します。 もう少し具体的に説明しましょう。

w' alpha w'' => w' beta w''生成する手順は、alpha- alpha --> beta generationルールに従って、 alphaサブチェーンをbetaサブチェーンに置き換えることです。 この場合、明らかに、チェーンw' alpha w'' 、チェーンw' beta w'' w' alpha w''取得します。 つまり、チェーンがあり、そのサブチェーンの一部が文法規則の左側にある場合、この左側の規則を右側に置き換える権利があります。 生成ステップの最後のシーケンスは、生成と呼ばれます。 ゼロ以上のクリーチャーは=>*示されます。 指定alpha =>* betaは、生成規則に基づいて有限数の順列によってalphaチェーンからbetaチェーンが取得されることを示します。 この表記では、置換（生成）が一度も適用されていない可能性があります。この場合、 alphaチェーンはbetaと一致しています。

したがって、生成文法G = {N, T, P, S}の言語は、終端記号で構成され、文法の初期記号から生成されたチェーンのセットです。 数式は次のとおりですL = {w | S =>* w} L = {w | S =>* w} 。

説明のために、2つの簡単な例を示します。

非常に単純な言語の例

言語Lを1つのチェーンで構成し、単一のシンボルaで構成aます。 つまり、 L = {a}です。 チェーンを生成するには、1つのルールS --> a十分です。 この文法に含まれる唯一の製品はS => aです。

この言語では、別の非終端記号、たとえば記号A 、および規則S --> AおよびA --> a S --> Aを導入できることに注意してください。 その場合、唯一の結果は次のようになります： S => A => a 。 非終端文法のアルファベットは任意に選択するため、このような単純な言語であっても、この言語を定義する生成文法は無限にあることが明らかになります。

簡単な算術式言語

言語A = {a+a, a+a+a, a+a+a+a, ...}考えてみましょう。 この言語のチェーンは、 +文字で区切られた文字シーケンスaです。 この言語を生成するためのルールを設定する方法は？ 各言語チェーンはa始まりaその後に1つ以上のチェーン+a続くことに注意してください。 したがって、最初にシンボルa生成し、次にこのシンボルの右側に1つ以上のチェーン+aを付加することにより、言語の各チェーンが生成されるというアイデアが生まれます。 これら2つの生成段階を互いに分離するために、非終端記号Aを導入しますA 次に、 S --> aA, A --> +aA, A --> +aルールを持つ文法を取得S --> aA, A --> +aA, A --> +aます。

たとえば、チェーンa+a+aを生成する方法を考えます。 S => aA => a+aA => a+a+a この世代では、 S --> aA, A --> +aA, A --> +a 3つのルールすべてが連続して適用されましS --> aA, A --> +aA, A --> +a 。

言語Aには無限の数のチェーンが含まれています。つまり、この言語ではチェーンの長さに制限はありません。 無制限の長さのチェーンをスポーンする唯一の方法は、再帰スポーンルールを使用することです。 ルールの右側に左側が含まれるルール。 上記の例では、このルールはA --> +aAです。 左側は、右側にも含まれる単一のシンボルAチェーンです。 この再帰により、置換に同じルールを一貫して適用し、必要に応じて生成されたチェーンの長さを増やすことができます。 再帰は、中間ルールを介して間接的に行うこともできます。 たとえば、ルールA --> aBc, B --> deAは、チェーンA間接再帰を指定しますA

文法クラス

Noam Chomskyは、生成する文法のルールの形式に制限を設定することにより、文法クラス（および対応する言語クラス）を導入しました。 文法の各クラスには、独自の記述力があります。 文法のクラスの記述力は、特定の構文関係の文法規則における表現の可能性として特徴付けることができます。 文法クラスが構文関係を定義する方法を検討してください。

文法タイプ3

このクラスの文法は、生成されたチェーンの右端または左端から一定数の終端記号を付加することにより、チェーンを生成するアルゴリズムを定義します。 明らかに、このような生成方法の規則は、 A --> alpha BまたはA --> B alphaの形式である必要があります。ここで、 alphaは終端記号で構成されるチェーンです。 この場合、（生成の過程で）チェーンX1..Xn Aが存在する場合、ルールA --> alpha Bに従って置換すると、チェーンX1..Xn alpha B A --> alpha Bが得られますX1..Xn alpha B たとえば、ルールS --> aaaA 、 A --> abcAおよびA --> bbb場合、世代S => aaaA => aaaabcA => aaaabcbbbを指定できます。

タイプ3の文法によって与えられる構文関係は、「近くに」という用語で表すことができます。 ここで「近く」とは、何らかの生成ルールの右側で指定されている場合はそのすぐ隣に、関連する生成ルールの非終端記号を介して間接的には隣にあることを意味します。

数学的厳密さのために、文法タイプ3の規則の終端記号の文字列は、右側に1つの終端記号があるいくつかの規則に分割されます。 たとえば、ルールA --> abcBがある場合、次のルールに置き換えることができます。その結果、アプリケーションは同じチェーンを生成します： A --> a A1 、 A1 --> b A2 、 A2 --> cB つまり、順列A => abcB 、順列A => a A1 => ab A2 => abcBです。 このような文法は、非終端記号がルールの右側の右側にある場合、右線形文法と呼ばれます。右側の非終端記号が端末の左側にある場合、その文法は左線形と呼ばれます。

たとえば、言語A = {a+a, a+a+a, a+a+a+a, ...}左線形文法を設定してみましょう。 前述のタイプ3の文法規則は、 S --> aA, A --> +aA, A --> +aです。 ここで、チェーンは、文字のペアを右側に追加することによって生成されます。 文字が左側で結合するように文法を変更し、非終端文字も追加して、毎回1​​文字のみを追加します。 文法を取得する：
S --> Aa
A --> B+
B --> Aa
B --> a
これは、チェーンa+a+aの生成方法です： S => Aa => B+a => Aa+a => B+a+a => a+a+a

注意深い読者は、おそらくタイプ3文法が生成オートマトンに似ていることに気付いたでしょう。生成オートマトンでは、非終端文法シンボルが状態の役割を果たします。 この文法の考えられる解釈の1つは、実際には有限状態マシンです。

文脈自由文法

文脈自由文法には、 A --> alphaという形式の規則があります。 ルールの左側には1つの文字（もちろん、非終端文字）があり、右側には終端文字と非終端文字のチェーン（空の文字を含む）があります。

KS文法は、2つのタイプの構文関係を定義します。「近くになる」関係と「一部になる」関係、または階層の関係です。 階層の関係は、人間の心にとって最も自然です。 物事を類型化するのは人間の性質です。 一般的なタイプ（クラス）の一部として、思考の特定のオブジェクトを考慮してください。 人が考えるすべてのものは、特定のクラスのインスタンスです。 たとえば、特定の椅子は、対応する特性を持つ「椅子」クラスのインスタンスです。 また、人間の心はタイプをサブタイプに分割し、より具体的なタイプからより抽象的なタイプに移行することも一般的です。 椅子は家具タイプのサブタイプ、家具はタイプオブジェクトのサブタイプ、オブジェクトはタイプオブジェクトのサブタイプなどであるとします。 「type-subtype」という関係は、階層の関係です。

KS文法は、カテゴリ文法、つまり 文法タイプ。 この場合の文法記号はタイプと考えることができ、ルールはタイプ間の階層関係を指定します。 非終端記号は複合型として機能し、終端記号はサブタイプを持つことができないアトミック型として機能します。 このKS文法の解釈は非常に人気があり、言語翻訳者の作成によく使用されます。 しかし、KS文法のクラスを設定することで、チョムスキーは何か他のものを意味しました。

KS-grammarは生成的であるため、言語のチェーンを生成するアルゴリズム（厳密には、アルゴリズムではなく、微積分は多変量アルゴリズムです）を定義します。 ここでのスポーンは、既存のチェーンの右または左にチェーンを結合するだけでなく、既存のチェーン内のどこかにチェーンを挿入することによっても定義されます。 挿入は、チェーン内の非終端記号を、あるルールの右側にあるチェーンに置き換えて行われます。その左側には、この非終端記号があります。 ルールA --> aaaがある場合、 aabBBaaaCbbbチェーンをaabBBaaaCbbbチェーンに変換できるとしましょう。 この意味で、生成されたチェーンはエッジから均等に成長するのではなく、内部から何らかの形で「膨張」します。

これまでに言われたことを例で説明します。 言語L = {a^nb^n | n = 1, 2, 3,...} L = {a^nb^n | n = 1, 2, 3,...} ここでの式a^nは、文字aをn回繰り返すことを意味aます。 したがって、言語Lは、 ab, aabb, aaabbbなどの形式のチェーンで構成されます。 この言語のKS文法を定義します。 これを行うには、言語チェーンから、シンボルbを左側の最初に、シンボルbを右側に追加することにより、別の言語チェーンを取得できることに注意してください。 aabbチェーンがある場合は、そこからaaabbbチェーンを取得できます。 この発言は、生成規則S --> aSb （言語のチェーンは、文法の最初の非終端から生成されるため、この記号で表すことができます）。 小さなチェーンに分割できない特殊なケースもあります-これはabチェーンです。 生成のためにルールS --> abを導入します。 そのため、言語の文法にはS --> aSbおよびS --> abというルールがあります。 チェーン生成aaabbb設定しましょう： S => aSb => aaSbb => aaabbb

文脈依存文法と制限なしの文法

CS文法の規則では、生成規則の左部分の非終端記号は、生成されたチェーンのどこでも、この記号が発生する場所であればどこでも右部分に変更できます。 しかし、時には、シンボルがチェーン内にあるコンテキストを区別したい場合があります。場合によっては、シンボルを置き換えます。 COP文法の規則ではこれが許可されていないため、このような場合には特別な種類の規則が必要です。

文脈依存文法には、 w' A w'' --> w' alpha w''という形式の規則があります。 ここで、 w'およびw''は、文法の終端記号と非終端記号で構成されるチェーン（空にすることができます）、 alphaは同じ記号の空でないチェーンです。 つまり、非終端記号Aは、チェーンw'およびw''のコンテキストでチェーンalphaに置き換えられます。

KZ文法に関連付けられているのは、別のクラスの文法、つまり短縮しない文法です。 このような文法のルールは、1つの条件を満たす必要があります。右側の長さは左側の長さ以上でなければなりません。 KZ文法の規則には、 alphaチェーンが空でないという条件があるため、これらの文法も短縮されません。 しかし、最も興味深いのは、非短縮文法で定義された各言語について、同じ言語を定義するKZ文法を発明できることです。 つまり、KZ文法と非短縮文法で定義される言語のクラスは一致します。

短縮しない文法で定義された言語のクラスを選択する必要があるのはなぜですか？ 実際、そのような言語では、認識マシンを指定できます。 文法の認識は次のように構築されます。入力としてチェーンを受け取り、生成されたチェーンの長さに沿って順序付けて製品を順番に作成します。 なぜなら 文法が短縮されない場合、そのような製品の有限セットが存在し、それらの間に特定の入力チェーンとの一致がなかった場合、「no」を出力します。

規則のタイプに制限のない文法の場合、一般的な場合のそのような認識アルゴリズムは構築できません。 生成されたチェーンは、生成プロセスでアコーディオン、膨張、収縮のように動作できます。 したがって、チェーンによって生成された特定の長さの達成は、入力に供給されたチェーンが生成プロセスでさらに受信されないことを保証しません。

KG言語は本当に独自のクラスを形成していますか？このクラスはKS言語のクラスと一致しますか？ つまり、KS文法は指定できないが、KZ文法は指定できることが保証されている言語はありますか？ 回答：はい、そのような言語があります。 このような言語の例は、次の言語L = {ww}です。 この言語のチェーンは、アルファベット上の2つの繰り返しチェーンで構成されています。 この言語のKS文法を構築することが不可能であることを証明するために、ここにはいません。 KZ文法は、次の考慮事項に基づいて定義できます。 まず、チェーンwと非終端記号、たとえばA生成します。 チェーンAw取得します。 次に、チェーンAを介してキャラクターAを進め、途中でこのチェーンのキャラクターのコピーを生成してから、これらのキャラクターを右に進めます。 以下の例で実装されるものとほぼ同じです。

言語L = {a^n^2 | n = 1, 2, 3, ...}文法を指定する例を考えてみましょうL = {a^n^2 | n = 1, 2, 3, ...} L = {a^n^2 | n = 1, 2, 3, ...} この言語のチェーンは文字aで構成され、これらの文字の数は自然数の2乗です：1、4、9、25など。 この言語の文法を制限なしに提供します。 チェーンの生成は、次の手順で構成されます。

1. 自然数nに対するn文字の生成。
2. この文字数n^2文字から生成します。
3. これらの文字を文字a変換aます。

最初の段階を実装するには、ルールを追加します
S --> LS'R
S' --> AS'B
S' --> AB

最初の規則は、生成されたチェーンを区切り文字LおよびRでラップすることですR 生成の第3フェーズの実装には、将来それらが必要になります。 残りの2つのルールは、文字AとB数が一致するAA...ABB...Bという形式のチェーンを単純に生成します。

ここで、文字列AA...ABB...B基づいてn^2文字を生成する必要がありAA...ABB...B これは簡単なトリックになります。 キャラクターB左に移動し、キャラクターB通過するたびに、別のキャラクターC生成しますC 文字Cを介して、文字Aは自由に右に、文字Bは左に自由に移動できます。 この手順のルールは次のとおりです。
AB --> BAC
AC --> CA
CB --> BC
Bすべての文字がAの文字を越えて左端に到達すると、 Cの文字は正確にn^2ます。

ここで、文字L 、 A 、 B 、 Rから解放し、文字Cを文字a変換する必要があります。 これを行うには、シンボルBが左端を通過するときに消滅させます。 キャラクターL したがって、右端のシンボルAで行動します。 このような戦略を実装する場合、 LCC....CRという形式のチェーンが残ります。 シンボルLおよびRを取り除くために、左のリミッターを右に動かし始め、それらが触れたときにこれらのシンボルを破壊します。 同時に、シンボルLを通過するときに、それらをシンボルa変換します。この生成フェーズのルールは次のとおりです。
LB --> L
AR --> R
LC --> aL
LR --> epsilon
ここではepsilon、空の文字列を指します。

チェーン生成の例を挙げましょうaaaa：S => LS'R => LAS'BR => LAABBR => LABACBR => LBACACBR => LACACBR => LACABCR => LACBACCR => LABCACCR => LBACCACCR => LACCACCR => LCACACCR => LCCAACCR => LCCACACR => LCCACCAR => LCCACCR => LCCCACR => LCCCCAR => LCCCCR => aLCCCR => aaLCCR => aaaLCR => aaaaLR => aaaa

おわりに

著者は、後者の例が、チョムスキーの生成文法がこの文法によって定義された形式言語のチェーンを生成するように設計された一種のプログラムであることを読者に明確に示したことを望んでいます。プログラム割り当ての言語はそれぞれ非常に具体的であり、「生成プログラム」（文法）の実装には、経験とそれらを書くための特定の習慣が必要です。

チョムスキーの生成文法は深いアイデアに基づいており、このタイプの文法のサブクラスの中には、特定の種類の言語を生成するだけでなく、数学言語学の他のセクションのアイデアと交差するものもあります。このようなセクションには、カテゴリ文法と認識オートマトンが含まれます。もちろん、このテキストでは基本的な考えのみが説明されています。生成文法の理論はより広く、より深いので、1つの記事の枠組みで説明することができます。