Need help with finite automata

[_dude_]

Hi guys. I'm reading a book called "Introduction to Automata Theory, Languages, and Computation (2 edition)" and got stuck a little bit with exercises for chapter 2, namely the exercise 2.2.5 (with an exclamation mark) a) and d) : Give DFA's accepting the following languages over the alphabet {0,1}:
a) The set of all strings such that each block of five consecutive symbols contains at least two 0's.
d) The set of strings such that the number of 0's is divisible by 5, and the number of 1's is divisible by 3.

I'm not asking for answers but for directions and helpful hints of solving those problems.

I have some thoughts regarding both problems but for me they seem very complicated and ugly. Thus, as for item a), I just build a transition diagram in the form of a binary tree of height 2^5 with transitions on 0 going to the left and transitions on 1 going to the right. And after that I mark all leaves within all branches of length five with at least two 0's as accepting states. After which from every accepting state I add another transition arc on 0 to the left node at level 2^1 and another transition arc on 1 to the right node at the same level (hence, to process another block of five consecutive symbols). Maybe there is a much simpler solution. Any ideas?

As for item b), how to count 0's and 1's at the same time without introducing new states for different number of 0's and 1's (i.e. a state for zero 0 and one 1, another state for two 0 and three 1's, another state for five 0's and three 1's, and so on)?

Thanks.

[Zeroth]

Well, as for A), I can say you're doing it the long, hard, complex way. Remember, a state can loop back to itself.

And for B ) exact same thing as above. You're making it harder than it is. States can loop back onto themselves, or to another state. So, really, you don't need a custom state.... just a way to count... think about you would count to 21 using your fingers only.

[OneOffDriveByPoster]

_dude_ @ Sat Sep 13, 2008 5:38 am wrote:

...another state for five 0's and three 1's, and so on)?

Think remainders.

[OneOffDriveByPoster]

_dude_ @ Sat Sep 13, 2008 5:38 am wrote:

a) The set of all strings such that each block of five consecutive symbols contains at least two 0's.

Is "0011111100" a member of that set?

(I admit that I am skipping your description of your DFA here).
I think it may be easier to try and match the complement of the set (given an alphabet of 0 and 1).

[bugzpodder]

a) this is equilvalent to saying any string without the substring 1111, 11011,11101 and 10111. If I counted correctly you can get away with about 10 states. in fact, this also give you a linear algorithm for string matching, slightly slower than KMP though.

d) It can be shown using the Myhill-Nerode Theorem that the minimum number of states any DFA would have is 3*5 = 15. Each state is exactly as you stated: a pair of integers (a,b) which consititutes number of 0s and 1s mod 5 and 3 resp

[_dude_]

Thank you guys for your replies. After some thinking over item a), I realized that I can drastically minimize my 2^5 binary tree by merging some states and eliminating redundant transition arcs. Thus, I ended up with a transition diagram with only 13 states. The only accepting state has two transition arcs back to state 1, where you get to if a block of 5 consecutive symbols starts with a zero, and state 2, where you get to if a block starts with a one. To prove correctness of this diagram I ran all 32 (32 is enough) binary strings (00000, 00001, ..., 11111) against it and every string with at least two 0's was accepted, whereas all the others were rejected. I guess this proof shows that my DFA will be in the accepting state only if a string has n blocks of 5 symbols and each block contains at least two 0's.

[OneOffDriveByPoster]

_dude_ @ Mon Sep 15, 2008 5:39 am wrote:

Thank you guys for your replies. After some thinking over item a), I realized that I can drastically minimize my 2^5 binary tree by merging some states and eliminating redundant transition arcs. Thus, I ended up with a transition diagram with only 13 states. The only accepting state has two transition arcs back to state 1, where you get to if a block of 5 consecutive symbols starts with a zero, and state 2, where you get to if a block starts with a one. To prove correctness of this diagram I ran all 32 (32 is enough) binary strings (00000, 00001, ..., 11111) against it and every string with at least two 0's was accepted, whereas all the others were rejected. I guess this proof shows that my DFA will be in the accepting state only if a string has n blocks of 5 symbols and each block contains at least two 0's.

That would be different from if every block of 5 was supposed to have at least two 0's. You can have a substring of length 5 starting from the second character for example.

[Zeroth]

Does your book cover proving the DFA is right by induction/logic? Because running all 32 possible states through it is proof by exhaustion. That is not to be mistaken with proof by student exhaustion, "Okay, we're going to into such excruciating detail for so long, all of you will fall asleep, and I don't need to actually do the proof."

[_dude_]

OneOffDriveByPoster, I thought of that that each block of five symbols could start at any position and I think you are right. I guess I have to redo my DFA.