コンテンツにスキップ

グライバッハ標準形

出典: フリー百科事典『ウィキペディア(Wikipedia)』

形式言語理論において、文脈自由言語の全ての生成規則が次のように書けるとき、グライバッハ標準形英語: Greibach normal form)であるという。

または

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

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

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

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

グライバッハ標準形の名前は、シーラ・グライバッハ英語版にちなんで名付けられたものである。

関連項目

[編集]