我正在为我的编译器类做一些考前练习，并且需要简化这个正则表达式。
(a U b)*(a U e)b* U (a U b)*(b U e)a*
很明显，e 是空字符串，U 代表联合。
到目前为止，我认为可以删除 (a U b)* 之一，作为 a U a = a 的并集。但是，我找不到任何其他简化，到目前为止，我在其他问题上做得并不好。:(
任何帮助表示赞赏，非常感谢！
问问题
1650 次
4 回答
3
首先翻译成该语言的英文描述：
(a U b)*(a U e)b* U (a U b)*(b U e)a*
转换为：
任何as 或bs 的序列，后跟一个可选的a，后跟任意数量的bs。
或者
任意数量的as 和bs，后跟一个可选的 s，后跟b任意数量的as
这里有很多重叠 - 至少(a U b)*(a U e)与 完全相同(a U b)*，因为“任何as 和bs 序列”必须以 ana或 epsilon 结尾（因为任何字符串都可以以 epsilon 结尾），因此可以消除这些组，留下
(a U b)*b* U (a U b)*a*
转换为：
as 或s 的任意序列b，后跟任意数量的bs。
或者
任意数量的as 和bs，后跟任意数量的as
现在最外层组的第一部分是相同的，所以让我们将它们折叠成一个
(a U b)*(a* U b*)
转换为：
as 或s 的任意序列b，后跟任意数量的as 或任意数量b的 s。
现在等一下，“A 和 B 的任何序列”必然以“ as 的任何序列或 s 的任何序列”结尾b，这意味着与第一部分匹配的任何内容都可以匹配整个正则表达式（因为第二部分可以有长度为零）所以我们为什么不做呢
(a U b)*
达达。简单的。
于 2011-02-10T02:01:18.563 回答
1
我认为整个事情相当于(a U b)*（或在大多数正则表达式语法中，(a|b)*）
于 2011-02-10T01:56:01.623 回答
1
正则表达式有点生疏，但如果 * 仍然代表“零次或多次出现”，您可以替换：
(a U e)b* for (a U b)*
剩下的第一部分是：
(a U b)*(a U b)* = (a U b)*
在右边，你有那个
(b U e)a* = (b U a)*
现在，由于 a U b = b U a，你得到：
(a U b)*(a U b)*
在右手边，只剩下
(a U b)* U (a U b)* = (a U b)*
我想就是这样...
于 2011-02-10T01:59:58.410 回答
0
我会给你一个我将如何解决它的想法：（不是很正式，也不能保证）
查看主U的左侧：
(a U b)* - 这是什么意思？长度为 n 的 a´s 和 b´s 的组合，其中 n >= 0。
接下来是（a U e）。我们有什么在这里？一个 a 或空词。如果我们想要它，我们可以在前面的部分中得到它。如果我们想要 e，那么无论如何我们都可以忽略它。请注意这里我们不必选择a，因为我们可以选择e。所以我们可以跳过这整个部分。
接下来是什么？乙*。那是什么？我们想要多少 b 就多少。我们也可以在第一部分得到那些！我们可以忽略它！
所以左边唯一的就是 (a U b)*。
让我们看一下右侧：
好的，现在这很容易，我们可以使用相同的想法，只是不同的字母。
我们也会以同样的方式得到 (a U b)*。
所以最后我们有 (a U b)* U (a U b)* 你知道它等于 (a U b)*。
于 2011-02-10T02:06:31.300 回答