gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-01 01:18:56 25 4
gpt4 key购买 nike

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

过去的试卷有问题

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 作为最小值。

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

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

谢谢。

最佳答案

iiii是等价的。

正则表达式都是“一串 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 的建议也不错。)

    关于regex - 识别等效的正则表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10446868/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com