グライバッハ標準形
提供: miniwiki
言語の理論（形式言語の理論）において、文脈自由言語の全ての生成規則が次のように書けるとき、グライバッハ標準形(Greibach normal form)であるという。
- [math]A \to \alpha X[/math]
または
- [math]S \to \varepsilon[/math]
ここではAは非終端記号、αは終端記号、Xは開始記号以外の非終端記号からなる文字列(空を含む)をあらわし、Sは開始記号、εは空をあらわす。
また、左再帰が許されないという点において特徴的である。
全ての文脈自由文法は等価なグライバッハ標準形の文法に書換えることができる(定義によっては 2番目のεへの規則を含まないこともあるが、この場合は空列を受理しない)。これは、任意の文脈自由言語が非決定性プッシュダウンオートマトンで受理できることの証明である。
グライバッハ標準形で与えられた文法とその文法によって導出できる長さ n の文字列が与えられたとき、この文法に基づいた与えられた文字列の下向き構文解析は深さ n までに終了する。
グライバッハ標準形の名前はシーラ・グライバッハにちなんで名付けられたものである。