本文概述
- 删除无用符号
- 消除ε的产生
- 删除单位生产
- G的每个变量（即非终结点）和每个终结点都出现在L中某个单词的推导中。
- X→Y不应有任何产物，其中X和Y是非末端的。
- 如果ε不是语言L，则不必是X→ε。
删除无用符号如果符号未出现在生产规则的右侧并且不参与任何字符串的派生，则该符号可能是无用的。该符号被称为无用符号。同样，如果变量不参与任何字符串的派生，则可能是无用的。该变量称为无用变量。
例如：
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】因此，最终我们可以编写没有单元生产的CFG为
S → 0A | 1B | 01
A → 0S | 00
B → 1 | 0S | 00
C → 01推荐阅读
- 自动机Chomsky范式（CNF）
- 自动机无歧义语法
- 自动机语法中的歧义
- 自动机推导树
- 自动机推导
- 自动机之Mealy机
- 自动机之Moore机
- 从Mealy机到Moore机的转换
- 从Moore机到Mealy机的转换