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 です。