黒田標準形

形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形（くろだひょうじゅんけい、Kuroda normal form）であるという。

AB → CD
A → BC
A → B
A → a

ここで A, B, C, D は非終端記号であり a は終端記号である。A → B はしばしば省略される。

言語学者黒田成幸の研究に基づくが、黒田自身はこれを線形有界文法（linear bounded grammar）と呼んだ。

黒田標準形をもつどんな文法もであり、したがって文脈依存言語を生成する。逆に、空文字列を含まないどんな文脈依存言語も、黒田標準形をもつ文法によって生成することができる。

György Révészによる素直な手法は、黒田標準形をチョムスキーの文脈依存文法の形に変換する。AB → CD は4個の文脈依存な規則 AB → AZ, AZ → WZ, WZ → WD, WD → CD に置き換えられる。この手法はまた、単調文法が文脈依存文法であることの証明にもなっている。

における似た標準形も存在し、こちらも複数の著者によって黒田標準形と呼ばれることがある。

AB → CD
A → BC
A → a
A → ε

ここで ε は空文字列である。これは、冒頭に挙げた文脈依存文法の黒田標準形に A → ε を加えただけのものである。どんな無制限文法もこの形式の生成規則のみを使う文法にである（すなわち同じ言語を生成するが、それぞれの導出木の形は異なるかもしれない）。もしも上記から規則 AB → CD が取り除けるならば、それは文脈自由文法となる（チョムスキー標準形）。

 Penttonen標準形 

黒田標準形の文脈依存な規則が AB → AD（左文脈依存、left context-sensitive）となるケースを特別にPenttonen標準形（Penttonen自身の用語によれば片側標準形、one-sided normal form）という。文脈依存文法におけるPenttonen標準形は次のとおりである。

AB → AD
A → BC
A → a

どんな文脈依存文法にも、それと弱等価なPenttonen標準形が存在する。黒田標準形の場合と同様に、これに A → ε を加えれば無制限文法におけるPenttonen標準形が得られる。

 参考文献 
 S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, June 1964.

 脚注 

 関連項目 
バッカス・ナウア記法
チョムスキー標準形
グライバッハ標準形

Category:形式言語
Category:数学に関する記事