黒田標準形
形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形(くろだひょうじゅんけい、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 が取り除けるならば、それは文脈自由文法となる。