正则表达式 – 表示等效的正则表达式

发布时间：2020-12-14 05:49:44 所属栏目：百科来源：网络整理

导读：我正在修改考试,其中一个主题是正则表达式. 过去的试卷有问题 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)* 我认为这是一个棘手

我正在修改考试,其中一个主题是正则表达式.

过去的试卷有问题

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的建议也很好.)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!