|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 標 ： [しるし] 【名詞】 1. (1) mark 2. (2) symbol 3. (3) evidence ・ 標準 ： [ひょうじゅん] 【名詞】 1. standard 2. level ・ 準 ： [じゅん] 1. (n,pref) level 2. apply correspondingly 3. correspond to 4. being proportionate to 5. conforming to 6. semi 7. quasi 8. associate 9. standard 10. rule 1 1. aim ・ 形 ： [けい, かたち, ぎょう] 1. (suf) shape 2. form 3. type
計算機科学において、文脈自由言語の全ての生成規則が次のように書けるとき、グライバッハ標準形(Greibach normal form)であるという。 : または : ここでは''A''は非終端記号、αは終端記号、''X''は開始記号以外の非終端記号からなる文字列(空を含む)をあらわし、''S''は開始記号、εは空をあらわす。 また、左再帰が許されないという点において特徴的である。 全ての文脈自由文法は等価なグライバッハ標準形の文法に書換えることができる(定義によっては 2番目のεへの規則を含まないこともあるが、この場合は空列を受理しない)。これは、任意の文脈自由言語が非決定性プッシュダウンオートマトンで受理できることの証明である。 グライバッハ標準形で与えられた文法とその文法によって導出できる長さ ''n'' の文字列が与えられたとき、この文法に基づいた与えられた文字列の下向き構文解析は深さ ''n'' までに終了する。 グライバッハ標準形の名前はシーラ・グライバッハにちなんで名付けられたものである。 == 関連項目 == * バッカス・ナウア記法 * チョムスキー標準形 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「グライバッハ標準形」の詳細全文を読む スポンサード リンク
|