黒田標準形
形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形（くろだひょうじゅんけい、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.
脚注
[編集]- ^ a b c Masami Ito; Yūji Kobayashi; Kunitaka Shoji (2010). Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008. World Scientific. p. 182. ISBN 978-981-4317-60-3
- ^ a b c d e Mateescu, Alexandru; Salomaa, Arto (1997). “Chapter 4: Aspects of Classical Language Theory”. In Rozenberg, Grzegorz; Salomaa, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. p. 190. ISBN 978-3-540-61486-9
- ^ Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2
- ^ a b Alexander Meduna (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 722. ISBN 978-1-85233-074-3
- ^ Alexander Meduna (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 728. ISBN 978-1-85233-074-3
- ^ Penttonen, Martti (1974-08-01). “One-sided and two-sided context in formal grammars” (英語). Information and Control 25 (4): 371–392. doi:10.1016/S0019-9958(74)91049-3. ISSN 0019-9958.