regex - 识别等效的正则表达式

Question

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

过去的试卷有问题

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)*

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

我会接受 aabaabaabaabbaabaabaabaabbaabaabaabaab 但 ii 和 iii 不会

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

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

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

谢谢。

Answer 1

i和 iii是等价的。

正则表达式都是“一串 a s 和 b s，其中至少有两个 b s”(从每个定义中都应该清楚这一点)。事实iii刚好a* s 代替前两个 (a+b)*是一种干扰。我会分解如何iii描述字符串:

一个可能为空的字符串 a s(以下标签中的 A)

第一 b ( X )

另一个可能为空的字符串 a s ( B )

第二个 b ( Y )

和字符串的其余部分只是 a 的混合s 和 b s ( 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 的建议也不错。)