Greibach 自动机范式 GNF

Question

格赖巴赫范式 GNF

GNF 代表 Greibach 范式。如果所有生产规则都满足以下条件之一，则 CFG (上下文无关语法) 为 GNF(Greibach 范式)：

• 起始符号生成ε。例如，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

由于给定的语法 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 形式。