乔姆斯基范式 (CNF)

CNF 代表乔姆斯基范式。 如果所有产生式规则满足以下条件之一，则 CFG（上下文无关文法）处于 CNF（乔姆斯基范式）：

• 开始符号生成 ε。 例如，A → ε。
• 一个非终结符生成两个非终结符。 例如，S → AB。
• 一个非终结符生成一个终结符。 例如，S → a。

例如

文法 G1 的产生式规则满足 CNF 的指定规则，因此文法 G1 处于 CNF。 但是，文法 G2 的产生式规则不满足 CNF 的指定规则，因为 S → aZ 包含终结符后跟非终结符。 因此，文法 G2 不在 CNF 中。

将 CFG 转换为 CNF 的步骤

步骤 1： 从 RHS 中删除开始符号。 如果开始符号 T 在任何产生式的右侧，则创建一个新的产生式为

其中 S1 是新的开始符号。

步骤 2： 在文法中，删除空产生式、单元产生式和无用产生式。 您可以参考 CFG 的简化。

步骤 3： 如果它们与其他非终结符或终结符一起存在，则从产生式的 RHS 中删除终结符。 例如，产生式 S → aA 可以分解为

步骤 4： 删除 RHS 中包含两个以上非终结符的产生式。 例如，S → ASB 可以分解为

示例

将给定的 CFG 转换为 CNF。 考虑给定的文法 G1

解决方案

步骤 1： 我们将创建一个新的产生式 S1 → S，因为开始符号 S 出现在 RHS 上。 文法将是

步骤 2： 由于文法 G1 包含 A → ε 空产生式，从文法中删除它会产生

现在，由于文法 G1 包含单元产生式 S → B，删除它会产生

同时删除单元产生式 S1 → S，从文法中删除它会产生

步骤 3： 在产生式规则 S0 → aA | Aa, S → aA | Aa, A → aBB 和 B → Aa 中，终结符 a 与非终结符一起存在于 RHS 上。 因此，我们将用 X 替换终结符 a

步骤 4： 在产生式规则 A → XBB 中，RHS 包含两个以上的符号，从文法中删除它会产生

因此，对于给定的文法，这就是所需的 CNF。