グライバッハ標準形

形式言語理論において、文脈自由文法は、すべての生成規則の右辺が終端記号で始まり、必要に応じて非終端記号が続く場合、グライバッハ標準形（GNF ）である。非厳密形式では、この形式の制約に例外を設け、空語（イプシロン、ε）を記述対象の言語の要素として認めることができる。この標準形はシーラ・グライバッハによって確立され、彼女の名にちなんで名付けられている。

より正確には、文脈自由文法は、すべての生成規則が次の形式である場合にグライバッハ標準形である。

${\displaystyle A\to aA_{1}A_{2}\cdots A_{n}}$

どこ${\displaystyle A}$は非終端記号です。${\displaystyle a}$は終端記号であり、 ${\displaystyle A_{1}A_{2}\ldots A_{n}}$は、（空の場合もある）非終端記号のシーケンスです。

文法には左再帰がないことに注意してください。

すべての文脈自由文法は、グライバッハ標準形の同等の文法に変換できます。^{[ 1 ]}さまざまな構成が存在します。ルールの 2 番目の形式を許可しないものもあり、空語を生成できる文脈自由文法を変換することはできません。そのような構成の 1 つでは、構築された文法のサイズは、一般の場合は O ( n ⁴ )、元の文法の導出が単一の非終端記号で構成されていない場合はO( n ^{3 ) になります。ここで、} nは元の文法のサイズです。^{[ 2 ]}この変換を使用して、すべての文脈自由言語がリアルタイム (非決定性)プッシュダウン オートマトンによって受理されることを証明できます。つまり、オートマトンがステップごとに入力から文字を読み取ります。

GNF の文法と、長さnの文法内の導出可能な文字列が与えられた場合、任意のトップダウン パーサーは深さnで停止します。

文法をグライバッハ標準形に変換する場合、すべての生成規則において右辺に非終端記号が最大で2つしか出現しないようにすることも可能です。これは二次グライバッハ標準形と呼ばれます。

文脈自由文法は、すべての生成規則が次の2つの形式のいずれかをとる場合、二重グライバッハ標準形である。

${\displaystyle A\to aA_{1}A_{2}\cdots A_{n}b}$

${\displaystyle A\to a}$

どこ${\displaystyle A}$は非終端記号です。${\displaystyle a,b}$は終端記号（必ずしも異なるとは限らない）であり、 ${\displaystyle A_{1}A_{2}\ldots A_{n}}$は、（空である可能性のある）非終端記号のシーケンスです。上記と同様に、各生成規則の右辺に非終端記号が最大で 2 つしか出現しない場合、文法は二次二重グライバッハ標準形になります。Hotz (1978) による古典的な結果では、空語を生成しないすべての文脈自由文法は、実質的に同等の二次二重グライバッハ標準形の文法に変換できるとされています。

• バッカス・ナウアー形式
• チョムスキー標準形
• 黒田ノーマルフォーム

• アレクサンダー・メドゥナ（2012年12月6日）。オートマタと言語：理論と応用。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-1-4471-0501-5。
• ジェルジ・E・レヴェシュ（2015年3月17日）形式言語の紹介。株式会社クーリエISBN 978-0-486-16937-8。
• Autebert, JM、Berstel, J.、Boasson, L. (1997)。文脈自由言語とプッシュダウンオートマタ。形式言語ハンドブック：第1巻 単語、言語、文法（pp. 111-174）。ベルリン、ハイデルベルク：Springer Berlin Heidelberg。