黒田標準形

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

AB → CD

A → BC

A → B

A → a

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

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

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

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

無制限文法（英語版）における似た標準形も存在し、こちらも複数の著者によって黒田標準形と呼ばれることがある^[4]。

AB → CD

A → BC

A → a

A → ε

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

Penttonen標準形

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

AB → AD

A → BC

A → a

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

参考文献

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