グライバッハ標準形のソースを表示

[[形式言語理論]]において、[[文脈自由言語]]の全ての[[形式文法#生成文法|生成規則]]が次のように書けるとき、'''グライバッハ標準形'''（{{Lang-en|Greibach normal form}}）であるという。

:<math>A \to \alpha X</math> 
または
:<math>S \to \varepsilon</math>

ここで、''A''は[[非終端記号]]、αは[[終端記号]]、''X''は開始記号以外の非終端記号からなる文字列（空を含む）をあらわし、''S''は開始記号、εは空をあらわす。

また、左再帰が許されないという点において特徴的である。

全ての文脈自由文法は等価なグライバッハ標準形の文法に書換えることができる（定義によっては2番目のεへの規則を含まないこともあるが、この場合は空列を受理しない）。これは、任意の文脈自由言語が[[プッシュダウン・オートマトン|非決定性プッシュダウンオートマトン]]で受理できることの証明である。

グライバッハ標準形で与えられた文法とその文法によって導出できる長さ ''n'' の文字列が与えられたとき、この文法に基づいた与えられた文字列の下向き[[構文解析]]は深さ ''n'' までに終了する。

グライバッハ標準形の名前は、{{Ill|シーラ・グライバッハ|en|Sheila Greibach}}にちなんで名付けられたものである。
== 関連項目 ==
* [[バッカス・ナウア記法]]
* [[チョムスキー標準形]]

{{DEFAULTSORT:くらいはつはひようしゆんけい}}
[[Category:形式言語]]
[[Category:数学に関する記事]]