0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.