4

我正在为上午考试复习，其中一个主题是正则表达式。

过去的试卷有问题

以下哪个正则表达式是等价的？解释你的推理。[8分]

(i) (a+b)* b (a+b)* b (a+b)*

(二) a* ba* ba*

(iii) a* ba* b (a+b)*

我认为这是一个棘手的问题，答案是否定的，因为

我会接受 aabaabaabaabbaabaabaabaabbaabaabaabaab 但 ii 和 iii 不会

那么因为 ii 只能接受 2 b 的最大值，而 iii 可以接受 2 b 的最小值。

我是对的还是我完全错了？

我已经通过电子邮件向我的讲师寻求帮助，但没有回复，所以我希望这里有人可以提供帮助。

谢谢。

4

1 回答 1

4

i并且iii是等价的。

正则表达式都是“一串as 和b至少有两个bs 的 s”（这在每个定义中都应该很清楚）。iii仅用a*s 代替前两个的事实(a+b)*令人分心。我将分解如何iii描述字符串：

  • 一个可能为空的as 字符串（A在下面的标签中）
  • 第一个b ( X)
  • 另一个可能为空的as ( B)字符串
  • 一秒钟b( Y)
  • 其余的字符串只是as 和bs ( C)的混合

对于您的示例，iii确实匹配它。想象一下我们这样标记正则表达式（v和^只是箭头）：

A  X B  Y   C
vv v vv v vvvvvv 
a* b a* b (a+b)*

然后我们可以标记正则表达式的哪一部分对应于字符串的各个部分：

  X  Y
  v  v
aabaabaabaabbaabaabaabaabbaabaabaabaab
^^ ^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
A   B            C

（@Li-aungYip 的建议也不错。）

于 2012-05-04T10:33:37.650 回答