Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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 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

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.
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.
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 think it may be easier to try and match the complement of the set (given an alphabet of 0 and 1).
bugzpodder

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
_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.
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.
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."

_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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 9 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: