自动机简化CFG

本文概述

• 删除无用符号
• 消除ε的产生
• 删除单位生产

如我们所见，各种语言可以有效地由上下文无关的语法表示。并非所有语法都总是经过优化的，这意味着语法可能包含一些额外的符号（非终结符）。具有多余的符号，不必要的增加了语法的长度。语法的简化意味着通过删除无用的符号来减少语法。简化语法的属性如下：

1. G的每个变量（即非终结点）和每个终结点都出现在L中某个单词的推导中。
2. X→Y不应有任何产物，其中X和Y是非末端的。
3. 如果ε不是语言L，则不必是X→ε。

让我们详细研究还原过程。/p>

删除无用符号

如果符号未出现在生产规则的右侧并且不参与任何字符串的派生，则该符号可能是无用的。该符号被称为无用符号。同样，如果变量不参与任何字符串的派生，则可能是无用的。该变量称为无用变量。

例如：

T → aaB | abA | aaT
A → aA
B → ab | b
C → ad

在上面的示例中，变量“ C”将永远不会出现在任何字符串的派生中，因此生产C→ad是无用的。因此，我们将消除它，并以这样的方式编写其他产生式：变量C永远不会到达起始变量“ T”。

生产A→aA也是无用的，因为没有办法终止它。如果它永远不会终止，那么它就永远不会产生字符串。因此，这种生产永远不能参与任何推导。

为了消除这种无用的生产A→aA，我们将首先找到所有永远不会导致终端字符串的变量，例如变量’A’。然后，我们将删除其中出现变量“ B”的所有产生式。

消除ε的产生

S→ε的生成称为ε生成。这些类型的产生式只能从不产生ε的语法中删除。

步骤1：首先找出所有可归纳的非终端变量，得出ε。

步骤2：对于每个产品A→a，构造所有产品A→x，其中x是通过从步骤1中移除一个或多个非末端而从a获得的。

步骤3：现在将步骤2的结果与原始产品合并，并删除ε产品。

例：

保留其含义，从以下CFG中删除产生的内容。

S → XYX
X → 0X | ε
Y → 1Y | ε

解：

现在，在消除ε产生的同时，我们将删除规则X→ε和Y→ε。为了保留CFG的含义，我们实际上在出现X和Y时将ε放在右侧。

让我们来

S → XYX

如果右边的第一个X是ε。然后

S → YX

同样，如果R.H.S.中的最后一个X =ε。然后

S → XY

如果Y =ε

S → XX

如果Y和X为ε

S → X

如果两个X都被ε替换

S → Y

现在，

S → XY | YX | XX | X | Y

现在让我们考虑

X → 0X

如果我们将ε放在X的右侧，

X → 0
X → 0X | 0

同样Y→1Y | 1个

总的来说，我们可以用除去ε的形式重写CFG为

S → XY | YX | XX | X | Y
X → 0X | 0
Y → 1Y | 1

删除单位生产

单位产品是一个非终端提供另一个非终端的产品。使用以下步骤删除单元生产：

步骤1：要删除X→Y，请在语法中出现Y→a时将生成X→a添加到语法规则中。

步骤2：现在，从语法中删除X→Y。

步骤3：重复步骤1和步骤2，直到删除所有单元产品为止。

例如：

S → 0A | 1B | C
A → 0S | 00
B → 1 | A
C → 01

解：

S→C是单位生产。但是在删除S→C时，我们必须考虑C给出的结果。因此，我们可以向S添加一条规则。

S → 0A | 1B | 01

同样，B→A也是单位产品，因此我们可以将其修改为

B → 1 | 0S | 00

因此，最终我们可以编写没有单元生产的CFG为

S → 0A | 1B | 01
A → 0S | 00
B → 1 | 0S | 00
C → 01