解释 TOC 中的乔姆斯基范式

  • Z时代
  • 2024-01-10
  • 分类：综合

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

以上是 解释 TOC 中的乔姆斯基范式 的全部内容， 来源链接： utcz.com/z/359261.html

回到顶部