本文概述
- 将CFG转换为GNF的步骤
- 起始符号生成ε。例如，S→ε。
- 生成终端的非终端。例如，A→a。
- 一个非终端生成一个终端，后面跟着任意数量的非终端。例如，S→aASB。
G1 = {S → aAB | aB, A → aA| a, B → bB | b}
G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}语法G1的生成规则满足为GNF指定的规则，因此语法G1在GNF中。但是，语法G2的生成规则不满足为GNF指定的规则，因为A→ε并且B→ε包含ε（仅起始符号可以生成ε）。因此语法G2不在GNF中。
将CFG转换为GNF的步骤步骤1：将语法转换为CNF。
如果给定的语法不在CNF中，请将其转换为CNF。你可以参考以下主题将CFG转换为CNF：Chomsky正常形式
步骤2：如果语法存在左递归，则将其消除。
如果上下文无关文法包含左递归，则将其消除。你可以参考以下主题来消除左递归：Left Recursion
步骤3：在语法中，将给定的生产规则转换为GNF形式。
如果语法中的任何生成规则不是GNF形式，请将其转换。
例：
S → XB | AA
A → a | SA
B → b
X → a解：
【自动机Greibach范式（GNF）】由于给定的语法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替换为：
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现在我们将删除零产生C→ε，我们得到：
S → aB | AA
A → aC | aBAC | a | aBA
C → AAC |AA
B → b
X → a生产规则S→AA不在GNF中，因此我们用A→aC |代替。 aBAC |一个|生产规则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 |代替。 aBAC |一个|生产规则C→AAC中的aBA为：
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形式。
