在 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 包含終結符後跟非終結符。

更新於:12-Jun-2021

10K+ 瀏覽量

激發你的事業

完成課程即可獲得認證

開始
廣告