World's most popular travel blog for travel bloggers.

Finding an automaton with a given number of states

, , No Comments
Problem Detail: 

Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^*$.

My main problem is that to check for a string of length 4 (0111) I need at least 5 states to begin with. So to my (novice) little brain the question seems wrong.

Asked By : Achshar
Answered By : Ran G.

Hint: for 0111 you need 4 transitions (one for each input letter). If you have a sequence of 5 separate states (which is probably your first try), than you will have 4 transitions between them. However, if you have 4 states connected in a circle, you will also have 4 transition between them...

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback