乔姆斯基范式
在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式：
- A → BC 或
- A → α 或
- S → ε
这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。
所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。
除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。
Chomsky 范式得名于诺姆·乔姆斯基，他是发明乔姆斯基层级的美国语言学家。
证明
[编辑]- 长度为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.)