乔姆斯基正常形式

在形式语言理论中，如果一个无语境语法G的所有生产规则都是这样的形式，那么它就被称为乔姆斯基正常形式。A→BC，或A→a，或S→ε。其中，A、B和C是非终端符号，字母a是终端符号（代表一个常量值的符号），S是起始符号，ε表示空字符串。另外，B和C都不可能是起始符号，第三条生产规则只有在ε在L(G)中时才能出现，L(G)是由无语境语法G产生的语言。每一个乔姆斯基正常形式的语法都是无语境的，反之，每一个无语境的语法都可以转化为一个等价的语法，该语法为乔姆斯基正常形式，其大小不超过原语法大小的平方。

为了将语法转换为乔姆斯基正常形式，需要按照一定的顺序应用一连串的简单转换；这在大多数自动机理论的教科书中都有描述。以下每个转换都建立了乔姆斯基正常形式所需的一个属性。开始：从右手边消除开始符号引入一个新的开始符号S0，和一个新的规则S0→S。这不会改变语法的生成语言，而且S0也不会出现在任何规则的右侧。术语：消除具有非孤岛终端的规则为了消除每条规则A→X1...a...Xn的每个规则，其终端符号a不是右侧的xxx符号，为每个这样的终端引入一个新的非终端符号Na，和一个新的规则如果右侧出现几个终端符号，同时用相关的非终端符号替换每个终端符号。这不会改变语法的生成语言。

BIN：消除右手边有2个以上的非终端符号替换每个规则要消除这种形式的所有规则，首先要确定衍生出ε的所有非终结符的集合。如果一个规则A→ε存在，那么A就是可空的。如果一个规则A→X1......获得一个中间语法，将每个规则替换为A→X1...Xn通过删除这个语法中的每条ε规则，除非其左侧是起始符号，否则就得到了转换后的语法。例如，在下面的语法中，起始符号为S0。S0→AbB|CB→AA|ACC→b|cA→a|ε除非这是一条已经（或正在）被删除的单元规则。由于B是非终端符号A的单元闭合的成员，因此在结果语法中跳过非终端符号B是可能的。

在选择上述变换的应用顺序时，必须考虑到一些变换可能会破坏其他变换所取得的结果。例如，如果START在UNIT之后应用，就会重新引入一个单位规则。该表显示了哪些顺序是被允许的。此外，语法大小的最坏情况下的膨胀取决于转换顺序。用|G|表示原始语法G的大小，最坏情况下的大小膨胀可能在|G|2到22|G|之间，这取决于使用的转换算法。语法大小的膨胀取决于DEL和BIN之间的顺序。当DEL首先完成时，它可能是指数级的，但在其他情况下是线性的。