1
$\begingroup$

$\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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Hiding in here is the classic postage stamp problem: Given a collection of 3-cent and 5-cent stamps, what amount of postage can you make? You can clearly make 0, 3, 5, 6, 8, 9, and 10. Since you can make 8, 9, and 10, you can make any larger amount by adding 3-cent stamps. For example, from 8, 9, 10, you can make 11 (= 3 + 8), 12 (= 3 + 9), 13 (= 3 + 10) and it's easy to see that you can continue this process to make any amount greater than or equal to 8.

Now the DFA is easy: Have nine states, $q_0, q_1, \dotsc,q_9$ where $q_i$ "remembers" that you've seen a string of length $i$ so far. The transitions will be $\delta(q_i, a) = \delta(q_i, b) = q_{i+1}$ for $i=0,\dotsc, 8$ and $\delta(q_8, a) = \delta(q_8, b) = q_8$. The final states will be $q_0, q_3, q_5, q_6, q_8$.

$\endgroup$
  • $\begingroup$ Thank you!! But you see what I add? I forgot to add it. Can you help me now? $\endgroup$ – stud1 Nov 12 '15 at 15:29
  • $\begingroup$ Just follow Ran G.'s hint. You've accepted it already, so what part don't you understand? $\endgroup$ – Rick Decker Nov 12 '15 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.