跳至內容

黑田範式

維基百科,自由的百科全書

計算機科學中,形式文法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.