Automata Theory 简明教程

Greibach Normal Form

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

A CFG is in Greibach Normal Form if the Productions are in the following forms −

A → b

A → bD1…Dn

S → ε

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

where A, D1,…​.,Dn are non-terminals and b is a terminal.

Algorithm to Convert a CFG into Greibach Normal Form

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

Step 1 − If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’ → S.

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

Step 2 − Remove Null productions. (Using the Null production removal algorithm discussed earlier)

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

Step 3 − Remove unit productions. (Using the Unit production removal algorithm discussed earlier)

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

Step 4 − Remove all direct and indirect left-recursion.

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

Step 5 − Do proper substitutions of productions to convert it into the proper form of GNF.

Problem

将以下 CFG 转换为 CNF

Convert the following CFG into CNF

S → XY | Xn | p

X → mX | m

Y → Xn | o

Solution

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

Here, S does not appear on the right side of any production and there are no unit or null productions in the production rule set. So, we can skip Step 1 to Step 3.

Step 4

Step 4

现在，替换以下内容：

Now after replacing

S → XY | Xo | p

X in S → XY | Xo | p

带有

with

mX | m

我们得到：

we obtain

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

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

然后替换以下内容：

And after replacing

Y → Xn | o

X in Y → Xn | o

为

with the right side of

X → mX | m

我们得到：

we obtain

Y → mXn | mn | o。

Y → mXn | mn | o.

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

Two new productions O → o and P → p are added to the production set and then we came to the final GNF as the following −

S → mXY | mY | mXC | mC | p

X → mX | m

Y → mXD | mD | o

O → o

P → p