CNFはチョムスキー標準形の略です。すべての生成ルールが次の条件のいずれかを満たしている場合、CFG (文脈自由文法) は CNF (チョムスキー正規形) になります。
- ε の生成を開始します。たとえば、A → ε。
- 2 つの非終端を生成する非終端。たとえば、S→AB。
- 端末を生成する非端末。たとえば、S→a。
例えば：
G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} 文法 G1 の生成規則は CNF に指定された規則を満たしているため、文法 G1 は CNF に含まれます。ただし、S → aZ には終端とそれに続く非終端が含まれるため、Grammar G2 の生成規則は CNF に指定された規則を満たしていません。したがって、文法 G2 は CNF にはありません。
ソフトウェアテストにおける回帰テスト
CFGをCNFに変換する手順
ステップ1： RHS から開始記号を削除します。開始記号 T がプロダクションの右側にある場合は、次のように新しいプロダクションを作成します。
S1 → S
ここで、S1 は新しい開始シンボルです。
ステップ2： 文法から、null、unit、および無駄な表現を削除します。 「CFG の簡略化」を参照してください。
Javaをアップグレードする方法
ステップ 3: ターミナルが他の非ターミナルまたはターミナルと一緒に存在する場合、プロダクションの RHS からターミナルを削除します。たとえば、プロダクション S → aA は次のように分解できます。
S → RA R → a
ステップ 4: 非終端が 3 つ以上ある RHS を削除します。たとえば、S → ASB は次のように分解できます。
S → RS R → AS
例：
指定された CFG を CNF に変換します。与えられた文法 G1 を考えてみましょう。
S → a | aA | B A → aBB | ε B → Aa | b
解決：
ステップ1： 右側に開始記号 S が表示されるので、新しいプロダクション S1 → S を作成します。文法は次のようになります。
S1 → S S → a | aA | B A → aBB | ε B → Aa | b
ステップ2： 文法 G1 には A → ε null 生成が含まれているため、これを文法から削除すると次のようになります。
Javaのソート文字列
S1 → S S → a | aA | B A → aBB B → Aa | b | a
さて、文法 G1 にはユニット生成 S → B が含まれているため、その除去は次のようになります。
S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a
また、単位生成 S1 → S を削除すると、文法からそれを削除すると、次のようになります。
S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a
ステップ 3: プロダクションルールでは S0 → aA |ああ、S → aA | Aa、A → aBB および B → Aa、端子 a は非端子のある RHS 上に存在します。そこで、端子 a を X に置き換えます。
ジャワのロゴ
S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a
ステップ 4: 生成ルール A → XBB では、RHS に 3 つ以上のシンボルがあり、文法生成から削除されます。
S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB
したがって、特定の文法にとって、これは必要な CNF です。