Designing an NFA that accepts binary strings divisible by 5 or 6

[Lolligirl]

Hello everyone! I'm trying to make a transition diagram for an NFA that accepts strings that are either divisible by 5 or by 6. Here's the specific question:

Question: Present a transition diagram for an NFA that recognizes the set of binary strings that starts with a 1 and, when interpreted as entering the NFA most to least significant digit, each represents a binary number that is divisible by either five or six. Thus, 101, 110, 1100, 1111 are in the language, but 111, 1011 and 11010 are not.

Here is my divisible by 5 NFA so far:
https://dl.dropboxusercontent.com/u/5778771/Divisibleby5.jpg

But I get lost in the possibilities as soon as I try to make one any higher than this, like one that does divisible by 6, and then thinking of how to combine it with this one! It seems like a mess and I would appreciate some ideas greatly! :D

 

[Evgeny.Makarov]

Your automaton for divisibility by 5 is correct. In general, to recognize binary numbers divisible by $d$, one needs states $0,\dots,d-1$ corresponding to remainders modulo $d$. The transition function is (the first argument is a state, the second one is an input):
\begin{align}
\delta(q,0)&=2q\text{ mod }d\\
\delta(q,1)&=(2q+1)\text{ mod }d
\end{align}

To construct an automaton recognizing the union of two regular languages, make a new state and add $\varepsilon$-transition to the initial states of the automata recognizing the two languages.

 

[I like Serena]

Hi Lolligirl!

Can you make a table? (Wondering)

Suppose you already have a number that has a remainder $r$ when divided by 6.
What will the remainder become if you add a $0$ at its end?
And what if you add a $1$ at its end?

I'm thinking of a table like:

\(\displaystyle \text{Remainders when dividing by }6\)
\begin{array}{|c|c|c|}
\hline
r & 2r+0 & 2r+1 \\
\hline
0 & 0 & 1 \\
1 & 2 & 3 \\
2 \\
3 \\
4 \\
5 \\
\hline
\end{array}

If you have such a table, it should become clear what the state machine should look like.

 

[awesome22]

I have created a NFA for divisibility by 5 and 6, separately, but am still a bit perplexed on how to union them together. You said, "To construct an automaton recognizing the union of two regular languages, make a new state and add ε-transition to the initial states of the automata recognizing the two languages.", but I don't entirely understand what that means. Does that mean you add a state to the end and link the final states of each to it? Also, when combining the NFA's together, I'm not sure what to do since for the numbers 0-5, there are multiple paths a 1 or 0 will lead you to, and you can only have one 1 and one 0 coming out of each state. Thanks in advance for your help!

 

[I like Serena]

I have created a NFA for divisibility by 5 and 6, separately, but am still a bit perplexed on how to union them together. You said, "To construct an automaton recognizing the union of two regular languages, make a new state and add ε-transition to the initial states of the automata recognizing the two languages.", but I don't entirely understand what that means. Does that mean you add a state to the end and link the final states of each to it? Also, when combining the NFA's together, I'm not sure what to do since for the numbers 0-5, there are multiple paths a 1 or 0 will lead you to, and you can only have one 1 and one 0 coming out of each state. Thanks in advance for your help!

Put the two state machines next to each other.
Remove the 2 arrows that point to the respective initial states.
Create a new initial state.
Connect the new initial state to the original 2 initial states with an $\varepsilon$.

It means that you can take the path from the new initial state to either of the original state machines. You do this without reading anything.

 

[Lolligirl]

Oh my goodness, that's such a good way to look at it, Evgeny! I've seen those formulae before but I didn't realize what they're used for until now. Using your and I like Serena's help, here is my divisible by 6:
https://dl.dropboxusercontent.com/u/5778771/Divisibleby6.jpg

And using my divisible by 5 and divisible by 6, here's my overall NFA:
https://dl.dropboxusercontent.com/u/5778771/Divisibleby5or6.jpg

Do these seem okay at first glance? Would the new 0 state be an accepting state by itself? Thank you both again so much for helping me piece it together! :D

 

[Evgeny.Makarov]

Using your and I like Serena's help, here is my divisible by 6:

It looks OK, but I noticed that your problem statement says that strings should start with a 1. Therefore, the state corresponding to remainder 0 should not be initial. Instead, there should be a separate initial state that is not accepting. Since you are allowed to have an NFA, the only outgoing arrow from the initial state should be labeled with 1, and it should go to the state that corresponds to remainder 1.

Would the new 0 state be an accepting state by itself?

No, the new initial state in the automaton that recognizes the union should not be accepting.