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

In summary, To create an NFA that recognizes binary numbers divisible by either five or six, you can first create separate NFAs for divisibility by 5 and 6. Then, to combine them, create a new initial state and add an epsilon-transition to the initial states of the two NFAs. The state corresponding to remainder 0 in the divisibility by 6 NFA should not be initial, instead, there should be a separate initial state that is not accepting.
  • #1
Lolligirl
23
0
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
 
Technology news on Phys.org
  • #2
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.
 
  • #3
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.
 
  • #4
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!
 
  • #5
awesome22 said:
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.
 
  • #6
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
 
Last edited:
  • #7
Lolligirl said:
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.

Lolligirl said:
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.
 

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

1. How do you design an NFA that accepts binary strings divisible by 5 or 6?

To design an NFA that accepts binary strings divisible by 5 or 6, you can follow these steps:

  1. Create two states, one for numbers divisible by 5 and one for numbers divisible by 6.
  2. For the state representing numbers divisible by 5, create transitions for 0 and 1 that loop back to the same state.
  3. For the state representing numbers divisible by 6, create transitions for 0 and 1 that lead to the state representing numbers divisible by 5.
  4. Create a final state for both states.
  5. Set the start state to the state representing numbers divisible by 5.
This NFA will accept any binary string that is divisible by 5 or 6, as it will end in the final state for both states.

2. Can an NFA be designed to accept both binary strings divisible by 5 and 6 simultaneously?

Yes, it is possible to design an NFA that accepts both binary strings divisible by 5 and 6 simultaneously. You can create a single state with transitions for 0 and 1 that lead to the same state. This NFA will accept any binary string that is divisible by both 5 and 6.

3. How many states are needed to design an NFA that accepts binary strings divisible by 5 or 6?

The minimum number of states needed to design an NFA that accepts binary strings divisible by 5 or 6 is 2. This is because you only need a state for numbers divisible by 5 and a state for numbers divisible by 6. However, you can add more states for clarity or to make the NFA more efficient.

4. Is it possible to design a DFA that accepts binary strings divisible by 5 or 6?

No, it is not possible to design a DFA (Deterministic Finite Automaton) that accepts binary strings divisible by 5 or 6. This is because a DFA can only have one transition for each input symbol, while an NFA can have multiple transitions for the same input symbol.

5. Can an NFA be used to determine if a binary string is divisible by a number other than 5 or 6?

Yes, an NFA can be designed to accept binary strings divisible by any given number. You can follow the same steps as mentioned in the answer to question 1, but instead of creating states for numbers divisible by 5 and 6, you can create states for the given number. This NFA will accept any binary string that is divisible by the given number.

Similar threads

  • Programming and Computer Science
Replies
6
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
Replies
21
Views
4K
  • General Discussion
Replies
4
Views
7K
Back
Top