我正在修改考试,其中一个主题是正则表达式.
过去的试卷有问题
Which of the following regular expressions are equivalent? Explain
your reasoning. [8 Marks](i) (a+b)* b (a+b)* b (a+b)*
(ii) a* b a* b a*
(iii) a* b a* b (a+b)*
我认为这是一个棘手的问题,答案是没有,因为
我会接受aabaabaabaabbaabaabaabababaabaabaab但ii和iii不会
然后因为ii只能接受2 b的最大值而iii可以接受2 b的最小值.
我是纠正还是我完全错了？
我已经通过电子邮件向我的讲师寻求帮助,但没有回复,所以我希望有人可以提供帮助.
谢谢.
解决方法
我和iii是等价的.
正则表达式都是“as和bs的字符串,其中至少有两个bs”(这应该从每个定义中清楚). iii只是用* s代替前两个(a b)*的事实是一种分心.我将分解iii如何描述字符串：
>一个可能为空的字符串as(下面标签中的A)
>第一个b(X)
>另一个可能为空的字符串为(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的建议也很好.)
