World's most popular travel blog for travel bloggers.

[Solved]: Is it legal to draw an NFA with fewer nodes than what I normally see?

, , No Comments
Problem Detail: 

Is it Ok to express an NFA accepting 1*0 like the one above? All examples in books are represented like the bottom one. I'd like to know is that only a convention or it must have two extra nodes?

Two NFA representations

Asked By : pedim

Answered By : Renato Sanhueza

It is not a convention. You must know that a regular expression denotes one regular language and this language can be generated by an infinite number of differeny automatona (in this case we are talking about NFA).

Why are you always encountering the second automaton in the books? This is probably because the second automaton is obtained from the regular expression $1^*0$ using a well known method called Thompson's construction.

Which of the two automata is better? There isn't just one answer. The first NFA looks simpler but maybe you will have more work when you try to formally prove its correctness. In the other hand the second automaton looks more complex but it was obtained by a proven method so we are sure that it is correct.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53115

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback