在 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 包含终结符后跟非终结符。

Bhanu Priya

更新于：12-Jun-2021

10K+ 浏览量

激发你的事业

完成课程即可获得认证

开始