黑田範式
在計算機科學中,形式文法是 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.
這是一篇與電腦相關的小作品。您可以透過編輯或修訂擴充其內容。 |