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