黑田范式
在计算机科学中，形式文法是 Kuroda 范式的，当且仅当所有产生规则都有如下形式:
- AB → CD 或
- A → BC 或
- A → B 或
- A → α
这里的 A, B, C 和 D 是非终结符而 α 是终结符。
所有 Kuroda 范式的文法都是单调的，因此生成上下文有关语言。反过来说，所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。
参见
[编辑]引用
[编辑]- S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964.
 | 这是一篇與计算机相關的小作品。您可以通过编辑或修订扩充其内容。 |