Automata Theory 简明教程
CFG Simplification
在一个 CFG 中，所有产生式和符号可能不一定都用于推导字符串。此外，可能存在一些空产生式和单位产生式。消除这些产生式和符号被称为 simplification of CFGs 。简化主要包括以下步骤 −
-
Reduction of CFG
-
Removal of Unit Productions
-
Removal of Null Productions
Reduction of CFG
CFG 分为两个阶段来简化 −
Phase 1 − 从 CFG G 推导出一个等价文法 G’ ，使得每个变量都推导出某个终结符字符串。
Derivation Procedure −
步骤 1 − 包含所有推导出某个终结符的符号 W1 ，并初始化 i=1 。
步骤 2 − 包含所有推导出 Wi 的符号 Wi+1 。
步骤 3 − 增加 i 并重复步骤 2，直到 Wi+1 = Wi 。
步骤 4 − 包含所有包含 Wi 的产生式。
Phase 2 − 从 CFG G’ 推导出一个等价文法 G” ，使得每个符号都出现在句式中。
Derivation Procedure −
步骤 1 − 将起始符号包含在 Y1 中，并初始化 i = 1 。
步骤 2 − 包含所有可以从 Yi 推导出的符号 Yi+1 ，并包含所有已经应用的产生式。
步骤 3 − 增加 i 并重复步骤 2，直到 Yi+1 = Yi 。
Solution
Phase 1 −
T = {a, c, e}
根据产生式 A → a, C → c 和 E →aAa，W1 = {A, C, E}
根据产生式 S → AC，W2 = { A, C, E } U { S }
W3 = {A, C, E, S} U ∅
由于 W2 = W3，我们可以推导出 G' 为：
G' = {{A, C, E, S}, {a, c, e}, P, {S}}
其中 P：S → AC，A → a，C → c，E → aA | e
Phase 2 −
根据产生式 S → AC，Y1 = {S}
Y2 = {S, A, C}
根据产生式 A → a 和 C → c，Y3 = {S, A, C, a, c}
Y4 = {S, A, C, a, c}
由于 Y3 = Y4，我们可以推导出 G'' 为：
G'' = {{A, C, S}, {a, c}, P, {S}}
其中 P：S → AC，A → a，C → c
Removal of Unit Productions
任何形式为 A → B 的产生式，其中 A, B ∈ 非终结符被称作 unit production. 。
Removal Procedure −
Step 1 − 要消除 A → B ，只要在语法中出现 B → x 时，就添加到语法规则中产生式 A → x 。[x ∈ 终结符，x 可以为空]
Step 2 ——从语法中删除 A → B 。
Step 3 ——从步骤 1 开始重复，直到删除所有单位产生式。
Problem
从以下内容中删除单位产生式 -.
S → XY、X → a、Y → Z | b、Z → M、M → N、N → a
Solution −
语法中有 3 个单位产生式-
Y → Z、Z → M和 M → N
At first, we will remove M → N.
由于 N → a，我们添加 M → a，并删除 M → N。
产生式集变为
S → XY、X → a、Y → Z | b、Z → M、M → a、N → a
Now we will remove Z → M.
由于 M → a，我们添加 Z→ a，并删除 Z → M。
产生式集变为
S → XY、X → a、Y → Z | b、Z → a、M → a、N → a
Now we will remove Y → Z.
由于 Z → a，我们添加 Y→ a，并删除 Y → Z。
产生式集变为
S → XY、X → a、Y → a | b、Z → a、M → a、N → a
现在 Z、M和 N 不可达，因此我们可以删除它们。
最终的 CFG 没有单位产生式 -.
S → XY、X → a、Y → a | b
Removal of Null Productions
在 CFG 中，非终结符 ‘A’ 是一个空值变量，如果存在产生式 A → ε 或存在从 A 开始最终以
ε: A → …….… → ε
Removal Procedure
Step 1 结束的推导 - 找出导出 ε 的空值非终结符变量。
Step 2 - 对于每个产生式 A → a ，构建所有产生式 A → x ，其中 x 是通过从步骤 1 中移除一个或多个非终结符从 ‘a’ 获得的。
Step 3 - 将原始产生式与步骤 2 的结果合并，并移除 ε - productions 。
Problem
从以下内容中移除空值产生式 -
S → ASA | aB | b, A → B, B → b | ∈
Solution −
有两个空值变量 - A 和 B
At first, we will remove B → ε.
移除 B → ε 后，产生式集变为 -
S→ASA | aB | b | a，A ε B| b | &epsilon，B → b
Now we will remove A → ε.
去掉 A → ε 后，产生式集变为−
S→ASA | aB | b | a | SA | AS | S，A → B| b，B → b
这是去除空串转换的最终产生式集。