CODEWITHSUNDEEP
regex
TrueWheel
TrueWheel

Reputation: 987

Idetifying equivalent regular expressions

I am revising for am exam and one of the topics is regular expressions.

A past exam paper has the 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)*

I think its a trick question and the answer is none because

i will accept aabaabaabaabbaabaabaabaabbaabaabaabaab but ii and iii wont

then because ii can only accept 2 b's maximum and iii can accept 2 b's as a minimum.

Am I correct or have I got this completely wrong?

I have e-mailed my lecturer for help but had no reply so I'm hoping someone here can help.

Thanks.

Upvotes: 4

Views: 2016

Answers (1)

huon
huon

Reputation: 102216

i and iii are equivalent.

The regular expressions are both "a string of as and bs where there are at least two bs" (this should be clear from each definition). The fact that iii just has a*s in place of the first two (a+b)* is a distraction. I'll break down how iii describes the string:

  • a possibly empty string of as (A in the labelling below)
  • the first b (X)
  • another possibly empty string of as (B)
  • a second b (Y)
  • and the rest of the string which is just a mix of as and bs (C)

For your example, iii does match it. Imagine we labelled the regular expression like so (the v and ^ are just arrows):

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

Then we can label which part of the regex corresponds to the parts of the string:

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

(@Li-aungYip's suggestion is a good one too.)

Upvotes: 4

Related Questions