形式文法

次のような生成ルールがあると仮定します。

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ba}$

次に、 Sから始め、それに適用するルールを選択します。ルール 1 を選択すると、文字列aSbが得られます。次に、再びルール 1 を選択すると、S がaSbに置き換えられ、文字列aaSbbが得られます。次に、ルール 2 を選択すると、 S がbaに置き換えられ、文字列aababbが得られ、処理は完了です。この一連の選択を、記号を使ってより簡潔に記述できます。${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$。

文法の言語は無限集合である${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$、 どこ${\displaystyle a^{k}}$は${\displaystyle a}$繰り返し${\displaystyle k}$回数（そして${\displaystyle n}$特に、 は生成規則 1 が適用された回数を表します。この文法は文脈自由（左辺には単一の非終端記号のみが現れる）で、曖昧さがありません。

ルールが代わりに以下のようになっていると仮定しましょう。

1.${\displaystyle S\rightarrow a}$

2.${\displaystyle S\rightarrow SS}$

3.${\displaystyle aSa\rightarrow b}$

この文法は、規則 3 により文脈自由ではなく、規則 2 がシーケンスを生成するために使用できる複数の方法により曖昧です。${\displaystyle S}$s.

しかし、生成される言語は、単に空でない文字列の集合であり、${\displaystyle a}$s および/または${\displaystyle b}$s。これは簡単にわかります。${\displaystyle b}$から${\displaystyle S}$ルール2を2回使用して生成します${\displaystyle SSS}$ルール1を2回、ルール3を1回適用して${\displaystyle b}$これは、任意の空でないシーケンスを生成できることを意味します。${\displaystyle S}$s を s に置き換え、それぞれを s に置き換えます。${\displaystyle a}$または${\displaystyle b}$我々の好きなように。

同じ言語は、文脈に依存しない、曖昧さのない文法によっても生成できる。例えば、規則を持つ正規文法などである。

1.${\displaystyle S\rightarrow aS}$

2.${\displaystyle S\rightarrow bS}$

3.${\displaystyle S\rightarrow a}$

4.${\displaystyle S\rightarrow b}$

1950年代にノーム・チョムスキーによって最初に提案された生成文法の古典的な形式化では、 ^{[ 2 ] [ 3 ]}文法Gは次の要素から構成されます。

• Gから形成される文字列とは互いに素な、非終端記号の有限集合N。
• 有限集合${\displaystyle \Sigma }$Nと互いに素な終端記号の集合。
• 生成規則の有限集合Pで、各規則は次の形式である。

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

どこ${\displaystyle {*}}$はクリーネ星のオペレーターであり、${\displaystyle \cup }$は集合の和集合を表します。つまり、各生成規則は、ある記号列から別の記号列にマッピングします。最初の記号列（「先頭」）には、少なくとも1つの記号が非終端記号である限り、任意の数の記号が含まれます。2番目の記号列（「本体」）が空文字列のみで構成されている場合、つまり記号がまったく含まれていない場合は、特別な表記法（多くの場合）で表すことができます。${\displaystyle \Lambda }$、eまたは${\displaystyle \epsilon }$混乱を避けるために、このようなルールは消去ルールと呼ばれます。^{[ 4 ]}

• 際立ったシンボル${\displaystyle S\in N}$それは開始記号であり、文記号とも呼ばれます。

文法は正式にはタプルとして定義される。${\displaystyle (N,\Sigma ,P,S)}$このような形式文法は、文献では書き換えシステムまたは句構造文法と呼ばれることが多い。 ^{[ 5 ] [ 6 ]}

文法の動作は、文字列上の関係によって定義できる。

• 文法が与えられた場合${\displaystyle G=(N,\Sigma ,P,S)}$二項関係${\displaystyle {\underset {G}{\Rightarrow }}}$（「G は一段階で派生する」と発音）弦上で$\displaystyle (\Sigma \cup N)^{*}}$定義は以下のとおりです。

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• 関係${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$（G はゼロステップ以上で派生すると発音される）は、反射的推移閉包として定義される。${\displaystyle {\underset {G}{\Rightarrow }}}$
• 1文形式は$\displaystyle (\Sigma \cup N)^{*}}$開始記号から有限ステップで導出できる${\displaystyle S}$;つまり、文形式は${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$非終端記号を含まない文形式（つまり、$\displaystyle \Sigma ^{*}}$）は文と呼ばれます。^{[ 7 ]}
• 言語​​${\displaystyle G}$と表記される${\displaystyle {\boldsymbol {L}}(G)}$は、によって構築された文の集合として定義されます。${\displaystyle G}$。

文法${\displaystyle G=(N,\Sigma ,P,S)}$実質的にはセミ・トゥーシステム${\displaystyle (N\cup \Sigma ,P)}$文字列の書き換えは全く同じ方法で行われます。唯一の違いは、書き換えルールで置換する必要のある特定の非終端記号を区別し、指定された開始記号からの書き換えのみに関心がある点です。${\displaystyle S}$非終端記号を含まない文字列に変換します。

これらの例では、形式言語は集合構成記法を用いて指定されます。

文法を考慮する${\displaystyle G}$どこ${\displaystyle N=\left\{S,B\right\}}$、${\displaystyle \Sigma =\left\{a,b,c\right\}}$、${\displaystyle S}$は開始記号であり、${\displaystyle P}$以下の生成ルールで構成されます。

1.${\displaystyle S\rightarrow aBSc}$

2.${\displaystyle S\rightarrow abc}$

3.${\displaystyle Ba\rightarrow aB}$

4.${\displaystyle Bb\rightarrow bb}$

この文法は言語を定義する${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$どこ${\displaystyle a^{n}}$n 個の連続する文字列を表す${\displaystyle a}$'s。したがって、言語は 1 個以上の文字列の集合です。${\displaystyle a}$の後に同じ数の${\displaystyle b}$の後に同じ数の${\displaystyle c}$の。

文字列の派生の例をいくつか挙げます${\displaystyle L(G)}$は：

（表記法について：${\displaystyle P{\underset {i}{\Rightarrow }}Q}$（ 「文字列Pは生成規則iによって文字列Qを生成する」と読み、生成された部分は毎回太字で示されている。）

文脈自由文法とは、各生成規則の左辺が単一の非終端記号のみで構成される文法のことである。この制約は自明ではなく、すべての言語が文脈自由文法で生成できるわけではない。生成可能な言語は文脈自由言語と呼ばれる。

言語${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$上記で定義された言語は文脈自由言語ではなく、これは文脈自由言語のポンピング補題を用いて厳密に証明できるが、例えば言語は${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$（少なくとも1つ）${\displaystyle a}$続いて同じ数の${\displaystyle b}$'s) は文脈自由であり、文法によって定義できます${\displaystyle G_{2}}$と${\displaystyle N=\left\{S\right\}}$、${\displaystyle \Sigma =\left\{a,b\right\}}$、${\displaystyle S}$開始記号、および以下の生成ルール：

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ab}$

文脈自由言語は、${\displaystyle O(n^{3})}$アーリーの認識器などのアルゴリズムでは時間（ビッグオー記法を参照）で、高速行列乗算アルゴリズムでは3乗未満の時間で実現できます。^{[ 9 ]}つまり、あらゆる文脈自由言語に対して、文字列を入力として受け取り、時間で決定する機械を構築できます。${\displaystyle O(n^{3})}$文字列が言語のメンバーであるかどうかの時間、${\displaystyle n}$は文字列の長さです。^{[ 10 ]}決定論的文脈自由言語は、線形時間で認識できる文脈自由言語のサブセットです。^{[ 11 ]}この言語の集合またはそのサブセットを対象とするさまざまなアルゴリズムが存在します。

正規文法では、左辺は再び単一の非終端記号のみで構成されますが、今度は右辺にも制限が課されます。右辺は空文字列、単一の終端記号、または単一の終端記号の後に非終端記号が続く形式のいずれかであり、それ以外は許容されません。（より広い定義が用いられる場合もあり、より長い終端記号の列や、他の記号を含まない単一の非終端記号の列を許容することで、同じ言語クラスを定義しつつ、言語の表記を容易にすることができます。）

言語${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$上記で定義した言語は正規言語ではなく、${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$（少なくとも1つ）${\displaystyle a}$少なくとも1つが続く${\displaystyle b}$（数字は異なる場合がある）は、文法によって定義できるとおりである。${\displaystyle G_{3}}$と${\displaystyle N=\left\{S,A,B\right\}}$、${\displaystyle \Sigma =\left\{a,b\right\}}$、${\displaystyle S}$開始記号、および以下の生成ルール：

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

正規文法によって生成されたすべての言語は認識できます${\displaystyle O(n)}$有限状態機械による時間。実際には、正規文法は一般的に正規表現を使用して表現されますが、実際に使用されている正規表現の形式の中には、厳密には正規言語を生成しないものもあり、そのような逸脱のために線形認識性能を示さないものもあります。

チョムスキーの形式文法の階層構造に対する多くの拡張や変形が、言語学者とコンピュータ科学者の両方によって開発されてきた。その目的は、通常、表現力を高めるため、あるいは分析や構文解析を容易にするためである。開発された文法の形式には、以下のようなものがある。

• ツリー隣接文法は、書き換え規則が文字列だけでなく構文木にも作用できるようにすることで、従来の生成文法の表現力を向上させます。 ^{[ 12 ]}
• 接辞文法^{[ 13 ]}と属性文法^{[ 14 ] [ 15 ]}は、書き換え規則に意味属性と操作を追加することができ、文法の表現力を高めることと実用的な言語翻訳ツールを構築することの両方に役立ちます。

再帰文法とは、再帰的な生成規則を含む文法のことです。たとえば、文脈自由言語の文法は、非終端記号Aが存在し、それを生成規則に通してAを左端の記号とする文字列を生成できる場合、左再帰的であると言えます。^{[ 16 ]}再帰文法の例としては、2 つのコンマで区切られた文中の節が挙げられます。^{[ 17 ]}チョムスキー階層のすべてのタイプの文法は再帰的になり得ます。