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