黒田標準形
提供: miniwiki
2013/4/8/ (月) 19:58時点におけるja>Addbotによる版 (ボット: 言語間リンク 7 件をウィキデータ上の d:q1452617 に転記)
形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形（くろだひょうじゅんけい Kuroda normal form）であるという：
- AB → CD
- A → BC
- A → B
- A → α
ここで A, B, C, D は非終端記号であり α は終端記号である。
黒田標準形をもつ文法によって生成される言語は全て文脈依存言語である。逆に、空文字列を含まない文脈依存言語は全て黒田標準形をもつ文法によって生成することができる。
言語学者黒田成幸の研究に基づく。
参考文献
- S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, June 1964.