GNF はグライバッハ正規形の略です。すべての生成ルールが次の条件のいずれかを満たしている場合、CFG (文脈自由文法) は GNF (Greibach 標準形式) になります。

• εを生成するスタートシンボル。たとえば、S → ε。
• 端末を生成する非端末。たとえば、A → a。
• 任意の数の非終端が後に続く終端を生成する非終端。例：S→aASB。

例えば：

 G1 = aB, A → aA G2 = S → aAB 

文法 G1 の生成規則は GNF に指定された規則を満たしているため、文法 G1 は GNF にあります。ただし、文法 G2 の生成規則は、A → ε および B → ε に ε が含まれるため (ε を生成できるのは開始記号のみ)、GNF で指定された規則を満たしていません。したがって、文法 G2 は GNF にはありません。

CFG を GNF に変換する手順

ステップ1： 文法を CNF に変換します。

指定された文法が CNF にない場合は、CNF に変換します。 CFG を CNF に変換するには、次のトピックを参照してください: チョムスキー正規形

ステップ2： 文法が左再帰に存在する場合は、それを削除します。

文脈自由文法に左再帰が含まれている場合は、それを削除します。左再帰を排除するには、次のトピックを参照してください: 左再帰

ステップ 3: 文法では、指定された生成ルールを GNF 形式に変換します。

文法内の生成ルールが GNF 形式でない場合は、それを変換します。

例：

 S → XB | AA A → a | SA B → b X → a 

解決：

指定された文法 G はすでに CNF 内にあり、左再帰がないため、ステップ 1 とステップ 2 をスキップしてステップ 3 に直接進むことができます。

生成ルール A → SA は GNF にないため、S → XB | と置き換えます。プロダクション ルール A → SA の AA は次のようになります。

 S → XB | AA A → a | XBA | AAA B → b X → a 

プロダクション ルール S → XB および B → XBA は GNF にないため、プロダクション ルール S → XB および B → XBA の X → a を次のように置き換えます。

JavaScript文字列置換

 S → aB | AA A → a | aBA | AAA B → b X → a 

次に、左再帰 (A → AAA) を削除すると、次のようになります。

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

ここで、null 生成 C → ε を削除すると、次のようになります。

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

生成ルール S → AA は GNF にないため、A → aC | と置き換えます。アバック | |プロダクション ルール S → AA の aBA は次のようになります。

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

生成ルール C → AAC は GNF にないため、A → aC | と置き換えます。アバック | |プロダクション ルール C の aBA → AAC は次のようになります。

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

したがって、これは文法 G の GNF 形式です。