Automata Theory 简明教程

Greibach Normal Form

如果产生式具有以下形式，则 CFG 处于 Greibach 范式中 −

A → b

A → bD1…Dn

S → ε

其中 A、D1、…​、Dn 是非终结符，b 是终结符。

Algorithm to Convert a CFG into Greibach Normal Form

Step 1 − 如果起始符号 S 出现于某个右侧，创建一个新起始符号 S’ 和一个新产生式 S’ → S 。

Step 2 − 删除空产生式。（使用前面讨论的空产生式消除算法）

Step 3 − 删除单位产生式。（使用前面讨论的单位产生式消除算法）

Step 4 − 删除所有直接和间接左递归。

Step 5 − 适当替换产生式以将其转换为 GNF 的正确形式。

Problem

将以下 CFG 转换为 CNF

S → XY | Xn | p

X → mX | m

Y → Xn | o

Solution

在此， S 未出现在任何产生式的右侧，且产生式规则集中不存在单元或空产生式。因此，我们可以跳过步骤 1 到步骤 3。

Step 4

现在，替换以下内容：

S → XY | Xo | p

带有

mX | m

我们得到：

S → mXY | mY | mXo | mo | p。

然后替换以下内容：

Y → Xn | o

为

X → mX | m

我们得到：

Y → mXn | mn | o。

两个新的产生式 O → o 和 P → p 被添加到产生式集中，然后我们得出最终的 GNF，如下所示：

S → mXY | mY | mXC | mC | p

X → mX | m

Y → mXD | mD | o

O → o

P → p