in Theory of Computation
143 views
1 vote
1 vote

“Consider L = {w011w | w ∈ (o+1)*}.

Find minimum number of states that are required in DFA (L).”

Found this question in Made Easy Test Series and I think the question is incorrect, as the language is not regular. The solution of this question given by Made Easy is “L is a language, which contains all the strings containing substring 011.”

But for the given solution to be true L should be, L = {w011x | w,x ∈ (o+1)*}.

Request you all to provide your comments.

 

in Theory of Computation
143 views

2 Comments

edited by
Yes the language is not regular not even CFL
4
4
They forgot to differentiate between both w's. Clearly a misprint, but yeah you are correct, it is not Regular or even CFL. It is a CSL.
1
1

Subscribe to GO Classes for GATE CSE 2022

1 Answer

0 votes
0 votes
Yes, as this language not accepting 00111. This language is not even regular. This is CFL.

Related questions