- #1

Lolligirl

- 23

- 0

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