Cheap and Secure Web Hosting Provider : See Now

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 : http://cs.stackexchange.com/questions/50023

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback