Regular Expression Similarity Check

311 Views Asked by At

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question:

The regular expression 0*(10*)* denotes same set as:

  1. 0(0+10)*
  2. (0+1)10(0+1)
  3. (1*0)1
  4. None

The answer is option 3 yet I strongly feel option 4 as I was not able to create several strings constructed from the first expression to satisfy option 3. Any pointers would be helpful and also is there any easy way to solve these kind of problems?

Thanks.

2

There are 2 best solutions below

0
On

If I'm not missing something, then strings generated by option 3 must always end with a $\mathtt{1}$ while for the regex in question this is not necessary. So I'd agree with you that option 3 doesn't seem to be the right answer.

0
On

4 has to be correct, as the empty string is in $0^*(10^*)^*$ but not in 1, 2 or 3.