Need help with finite automata
Author |
Message |
_dude_
|
Posted: Sat Sep 13, 2008 5:38 am Post subject: Need help with finite automata |
|
|
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. |
|
|
|
|
![](images/spacer.gif) |
Sponsor Sponsor
![Sponsor Sponsor](templates/subSilver/images/ranks/stars_rank5.gif)
|
|
![](images/spacer.gif) |
Zeroth
|
Posted: Sat Sep 13, 2008 9:16 am Post subject: Re: Need help with finite automata |
|
|
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. |
|
|
|
|
![](images/spacer.gif) |
OneOffDriveByPoster
|
Posted: Sun Sep 14, 2008 8:15 am Post subject: Re: Need help with finite automata |
|
|
_dude_ @ Sat Sep 13, 2008 5:38 am wrote: ...another state for five 0's and three 1's, and so on)? Think remainders. |
|
|
|
|
![](images/spacer.gif) |
OneOffDriveByPoster
|
Posted: Sun Sep 14, 2008 8:20 am Post subject: Re: Need help with finite automata |
|
|
_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). |
|
|
|
|
![](images/spacer.gif) |
bugzpodder
![](http://www.vbforums.com/avatar.php?userid=31755&dateline=1038631511)
|
Posted: Sun Sep 14, 2008 2:44 pm Post subject: RE:Need help with finite automata |
|
|
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 |
|
|
|
|
![](images/spacer.gif) |
_dude_
|
Posted: Mon Sep 15, 2008 5:39 am Post subject: Re: Need help with finite automata |
|
|
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. |
|
|
|
|
![](images/spacer.gif) |
OneOffDriveByPoster
|
Posted: Mon Sep 15, 2008 8:13 am Post subject: Re: Need help with finite automata |
|
|
_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. |
|
|
|
|
![](images/spacer.gif) |
Zeroth
|
Posted: Mon Sep 15, 2008 10:11 am Post subject: Re: Need help with finite automata |
|
|
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." |
|
|
|
|
![](images/spacer.gif) |
Sponsor Sponsor
![Sponsor Sponsor](templates/subSilver/images/ranks/stars_rank5.gif)
|
|
![](images/spacer.gif) |
_dude_
|
Posted: Sat Sep 20, 2008 2:55 pm Post subject: Re: Need help with finite automata |
|
|
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. |
|
|
|
|
![](images/spacer.gif) |
|
|