CFG代表上下文无关文法，CNF代表计算理论中的乔姆斯基范式。
上下文无关文法 (CFG) 是一种形式文法，用于生成给定形式语言中所有可能的字符串模式。
它被定义为四个元组 -
G=(V,T,P,S)
在哪里，
G 是一个文法，由一组产生式规则组成。它用于生成语言的字符串。
T 是最终的终结符集。它用小写字母表示。
V 是最后一组非终结符。用大写字母表示
P 是一组产生式规则，用于将字符串中的非终结符（产生式左侧）替换为其他终结符（产生式右侧）。
如果产生式规则满足以下条件之一，则上下文无关文法在 CNF 中
如果有开始符号生成ε。示例 - A-> ε
如果一个非终结符产生两个非终结符。示例 - S->AB
如果一个非终端产生一个终端。示例 - S->a
按照下面给出的步骤成功地将 CFG 转换为 CNF： -
步骤 1 - 从右侧(RHS)消除开始符号
如果开始符号 S 在任何产生式的右侧，
创建一个生产如下 -
S1->S
其中，S1 是新的开始符号
第 2 步 - 在语法中尝试删除 null、unit 和无用的产生式。
步骤 3 - 如果终端与其他非终端或终端存在，则从生产的 RHS 中消除终端。
示例 - S->aA 可以分解如下 -
S->RA
R->a
最后，它只是 S->aA 而已。
步骤 4 - 消除具有两个以上非终端的 RHS。
示例 - S-> ABS 可以分解如下 -
S->RS
R->AB