微客导航 » 文章资讯 » 解释 TOC 中的乔姆斯基范式

解释 TOC 中的乔姆斯基范式

2023-06-07 16:32:04 481

乔姆斯基的范式代表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包含终结符后跟非终结符。