World's most popular travel blog for travel bloggers.

# Help with building a NFA automaton

, ,
Problem Detail:

$\Sigma=\{a,b\}$, $L=\{w\in \Sigma^* \Big| |w|=3n+5m, \ n,m\ge 0 \}$.
I need to build NFA automaton for $L$....

Now, I try it for hours but I don't have any idea how to solve it.
I know that any $x\ge 8$ can be written as $3n+5m, \ n,m\ge 0$ So, the automaton accepts any word the her length is 8 or higher, but it doesn't accepts words at length: 1,2,4,7.
One more rule: $|Q|=5$....

Can you help me please and guide me how should I solve it?
Because I don't have any idea so far...
Any automaton that I make accepts some of the words in the forbidden length...

Thank you!

###### Answered By : Ran G.

Just a hint:

If the requirement was to count the length $3n$, the NFA was simple, and could be done with 3 states. Similarly, if you only needed the $5m$ part, an easy 5-state NFA could do this.

Now think how to "combine" these two NFAs, one on top of the other. Use $\epsilon$-moves to go from the end of one, to the start of the another. Because you need $|Q|=5$, you will have to overload the meaning of 3 states so they serve both the $3n$ and the $5m$ machines.

Another hint that may be helpful: make $q_0$ accepting (and the only accepting state).

Good Luck.

Best Answer from StackOverflow

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

3200 people like this

#### Post a Comment

Let us know your responses and feedback