文脈自由言語
1. 序章
このチュートリアルでは、文脈自由言語について説明します。 特に、言語が文脈自由（ではない）であることを証明するためのいくつかの手法について説明します。
2. 文脈自由言語とは何ですか？
その質問に答える前に、まず形式言語と文法が何であるかを覚えておきましょう。
2.1. 言語と文法
形式言語は、空でない記号のアルファベットを使用して形成される単語のセットです。 たとえば、はアルファベット上の言語です。
すべての言語には文法があります。 非公式には、言語の文法は、その言語の単語を生成する方法を説明します。 正式には、これはタプルです。
- 文法が使用するすべての記号のセットです
- アルファベットです。 その記号を終端記号と呼びますが、の記号は非終端記号または変数として知られています
- すべての単語の派生を開始する一意の変数です
- 生産ルールのセットです
生産規則は、手元にある言語の単語を導き出します。したがって、それらは、単語の遷移形式から最終的な形への変換を導く規則と考えることができます。
たとえば、これらのルールは以下を生成します。
(1)
空の単語はどこにありますか。 したがって、の派生は次のとおりです。
プロダクションルールの形式に応じて、いくつかの文法と言語のタイプを区別します。
2.2. 文脈自由言語
プロダクションルールの形式が次の場合：
(2)
文法は文脈自由（CFG）であると言います。 したがって、言語を生成するCFGがある場合、その言語は文脈自由です。
前のセクションの言語は文脈自由です。 その文法は次のとおりです。
ここで、はルールのセット（ 1 ）です。 どちらのルールもCFG形式（ 2 ）であるため、コンテキストフリーであり、生成される言語もフリーです。
3. 言語が文脈自由であることを証明する方法
言語は、その単語の一般的なパターン（forなど）として暗黙的に記述することができます。 または、言語全体を含む明示的なコーパスを取得することもできます。
3.1. 文法の構築
私たちの言語がどのように述べられていても、その単語を生成するCFG文法を構築することにより、文脈自由であることを証明できます。
それは時々、口で言うほど簡単ではありません。 言語が複雑でない場合は、ルールを手動で導出できます（コンテキストがない場合）。 上記の例ではそうです。
ただし、言語の構造が複雑な場合は、対応するCFGの設計に苦労する可能性があります。 そして、それは手に入れるのが難しいルールだけではありません。 また、使用する非終端記号を決定する必要があります。 このような場合、自動文法学習の手法を適用できます。 単語のサンプルしか利用できない、部分的に記述された言語でも処理できます。
3.2. 文法が正しいことを証明する
CFGを考案するだけでは不十分です。 また、文法が言語を生成することと、言語のすべての単語を文法によって生成できることの2つのステートメントを証明する必要があります。 後者のみを証明することは、文法の言語にターゲット言語が含まれていることを示していますが、それらが等しいことは示していません。
まず、セクション2.2のルールを適用してそれを証明しましょう。 時々、私たちは単語または組み合わせのいずれかを取得します。 後者は非終端記号が含まれているため、単語ではありません。 適用されたルールの数による帰納によって、この仮説を証明します。
ベースケース（）では、またはを適用できます。 とはの形式なので、誘導ベースについて説明しました。
ステップケースでは、誘導仮説がいくつかに当てはまると仮定しているので、とがあります。 仮説は成り立ちますか？
に適用すると、が得られます。 同様に、他のルールを適用すると、が得られます。
したがって、が。の単語のみを生成することを示しました。
逆を証明する方が簡単です。 の単語はの形式です。 時間を適用し、その後、任意のを取得します。
3.3. プッシュダウンオートマタ
プッシュダウンオートマトン（PDA）は、文脈自由文法と同等の有限状態マシンです。 CFGによって生成される言語には、それを認識するPDAがあり、その逆も同様です。
場合によっては、文法よりもオートマトンを作成する方が簡単です。 非公式には、 PDAは有限状態マシンであり、入力からシンボルごとに単語を読み取り、スタックにシンボルを書き込みながら、状態間を遷移します。 単語全体を読み取り、スタックが空の受け入れ状態で終了する場合、読み取った単語が受け入れられたと言います。 PDAが認識する言語は、PDAが受け入れる単語で構成されています。
この記事ではPDAについては説明しませんが、PDAは確かに検討するための代替手段です。
3.4. 証明の質問
CFGまたはPDAを手動で作成できなかったからといって、言語が文脈自由ではないというわけではありません。証拠がないことは、証拠がないことと同じではありません。 私たちの言語を生成するCFGが存在する可能性がありますが、見つかりませんでした。
言語が文脈自由ではないために適切な文法を構築できなかったと思われる場合は、その言語が文脈自由ではないことを正確に証明することができます。
4. 言語が文脈自由でないことを証明する方法
オグデンの補題は、すべての文脈自由言語の特性を説明しています。 したがって、手元の言語にそのプロパティがないことを示すと、文脈自由ではないことが証明されます。
4.1. オグデンの補題
見出語を述べましょう。 文脈自由言語になりましょう。 次に、少なくとも位置（索引付き記号）がマークされているすべての単語（）が5つの部分に分割できるような自然数が存在します。
(3)
次のことが成り立つように：
- 少なくとも1つのマークされた位置が含まれています。
- 最大でマークされた位置が含まれます。
- すべてのために 。
見出語は、文脈自由言語の単語を生成する際の規則性を示しています。 選択したサブワード（および）をポンピングすると、その言語の新しいワードが生成されます。 少なくとも記号を含む単語がこの規則性を破る場合、その言語は文脈自由ではありません。
4.2. 文脈自由言語のポンピング補題
通常、すべての位置がマークされているオグデンの補題の特殊なケースを適用します。 このケースは、文脈自由言語のポンピング補題として知られています。
すべての文脈自由言語には、すべての単語（）が次のように記述できるような自然数が存在します。
次のことが成り立つように：
- すべてのために
4.3. 例
言語が文脈自由ではないことを証明しましょう。
したがって、最初に反対のこと、つまり文脈自由を想定します。 次に、ポンピング補題によって、でより短くないすべての単語を分割するという補題の条件を満たす必要があります。
単語に焦点を当てましょう。 見出語を適用すると、次のように書くことができます。
- すべてのために
最後の状態を分析してみましょう。 2つのオプションがあります。
- サブワードにはsのみが含まれます。 したがって、sとsの数は同じままで、ポンピングして単語内のsの数を増やします。 したがって、新しいポンプされた単語はに含まれません。
- または、sとsの両方を含めることができます。 サブワードとをポンピングすることにより、sの数、sの数、またはその両方を増やします。 同時に、sの数は同じままです。 したがって、この場合も、汲み上げられた単語は属しません。
これは文脈自由であると想定したため、矛盾しています。 したがって、仮定は間違っており、文脈自由言語にすることはできません。
4.4. 証明の質問、再考
対応するCFGとPDAを作成することによる証明の場合と同様に、言語が文脈自由でないことを証明できなかったからといって、それがであるとは限りません。 ポンピング特性を損なう単語が見つからなかったとしても、そのような単語が存在しないことを意味するわけではありません。
それは、両方の戦略が失敗した場合に何をすべきかという問題を開きます。 最善の行動は、自動学習者や定理証明者などのソフトウェアツールを使用することです。
5. 結論
この記事では、文脈自由言語について説明しました。言語を生成する文脈自由文法を構築すれば、言語が文脈自由であることを証明できます。 または、言語を認識するプッシュダウンオートマトンを作成することもできます。 一方、文脈自由言語の補題とポンピング補題を使用して、言語が文脈自由ではないことを証明します。
