解释 TOC 中的乔姆斯基范式

乔姆斯基的范式代表 CNF。

如果产生式规则满足以下条件之一，则上下文无关文法在 CNF 中

• 如果有开始符号生成ε。示例 - A-> ε

• 如果一个非终结符产生两个非终结符。示例 - S->AB

• 如果一个非终端产生一个终端。示例 - S->a

示例

让我们采用 G1 生产规则，如下所示 -

G1={ S->AB,
         S->c,
         A->a,
         B->b}

G1 满足为 CNF 指定的规则。所以，它在 CNF 中。

现在，让我们考虑 G2 产生式规则，如下所示

G2={ S->aA,
         A->a,
         B->c}

G2 不满足为 CNF 指定的规则，因为 S->aA 包含一个终端，然后是一个非终端。

所以，G2 不在 CNF 中

考虑另一个例子来检查给定的语法是否在 CNF 中。

语法如下 -

   S->a|aA|B
A->aBB| ε
B->Aa|b

给定的语法不在 CNF 中，因为 S->aA ,A->aBB, B->Aa 包含终结符后跟非终结符。