喬姆斯基範式
在計算機科學中，一個形式文法是 Chomsky 範式的，若且唯若所有產生規則都有如下形式：
- A → BC 或
- A → α 或
- S → ε
這裏的 A, B 和 C 是非終結符，α 是終結符（表示常量值的符號），S 是開始符號，而 ε 是空串。還有，B 和 C 都不可以是開始符號。
所有的 Chomsky 範式的文法都是上下文無關，反過來，所有上下文無關文法都可以有效的變換成等價的 Chomsky 範式的文法。
除了（在文法可能生成空串的時候包括的）可選規則 S → ε 是例外，Chomsky 範式的文法的所有規則都是擴張的，就是說在字符串的整個導出過程中，每個終結符和非終結符的字符串比起前面導出的字符串要麼同樣長度要麼多出一個元素。長度 n 的字符串的導出總是精確的 2n-1 步長。
證明
編輯- 長度為n個字符串需要n次A → α 的派生，因此需要n個語法變元；
- n個變元需要n-1次A → BC 的派生（從S開始，每次派生增加1個變元，增加n-1次）；
- 由1.、2.得知，長度為n且滿足喬姆斯基範式語法的字符串恰好需要2n-1次派生。
進一步的，因為導出非終結符的所有規則都把一個非終結符變換成兩個非終結符，基於 Chomsky 範式的文法上的一個分析樹是二叉樹，而這個樹的高度被限制於最高為這個字符串的長度。
由於這些性質，在語言和可計算性領域中很多證明採用了 Chomsky 範式。這些性質還產生了基於 Chomsky 範式的文法的各種有效算法；例如，判定給定字符串是否可以被使用 Chomsky 範式的給定文法生成的 CYK算法。
可替代的定義
編輯某些來源以稍微不同的方式來定義 Chomsky 範式：
一個形式文法是 Chomsky 範式的，若且唯若所有產生規則都有如下形式：
- A → BC 或
- A → α
這裏的 A, B 和 C 是非終結符，而 α 是終結符。當使用這個定義的時候，B 和 C 不能是開始符號。
這個定義不同於前面定義的是它排除了文法生成空串 ε 的可能性。接受一個語言 L 的任何上下文無關文法都可以有效的變換成接受 L - {ε} 的 Chomsky 範式的文法。後者定義的首要好處是證明通常更簡單，由於在導出過程中每個步驟都永不減少結果字符串的長度。當然它的缺點是在最初文法生成 ε 就需要特殊考慮。
參見
編輯引用
編輯- Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. (Pages 98–101 of section 2.1: context-free grammars. Page 156.)
- John Martin. Introduction to Languages and the Theory of Computation. McGraw Hill. 2003. ISBN 0-07-232200-4. (Pages 237–240 of section 6.6: simplified forms and normal forms.)
- John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 4.)