乔姆斯基范式
在计算机科学中,一个形式文法是 Chomsky 范式的,当且仅当所有产生规则都有如下形式:
这里的 A, B 和 C 是非终结符,α 是终结符(表示常量值的符号),S 是开始符号,而 ε 是空串。还有,B 和 C 都不可以是开始符号。
所有的 Chomsky 范式的文法都是上下文无关,反过来,所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。
除了(在文法可能生成空串的时候包括的)可选规则 S → ε 是例外,Chomsky 范式的文法的所有规则都是扩张的,就是说在字符串的整个导出过程中,每个终结符和非终结符的字符串比起前面导出的字符串要幺同样长度要幺多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。