CODEWITHSUNDEEP
regular-languagefinite-automatacomputation-theorydfa
walt disney
walt disney

Reputation: 29

Need to construct DFA (deterministic finite automaton)

I need to construct a DFA which recognises all the strings made solely from 0s and 1s, so that thay have an even number of zeros and number of ones divisible by 3. I found an automaton for the case of even number of 0s and even number of 1s:

automaton for even number of 0s and 1s

I tried going from here by adding some states, changing branches, etc.. However I remained unsuccessful usually losing track of what's the automaton doing beacuse of branches and states I'd add. Any help would be greatly appreciated.

Upvotes: 0

Views: 1558

Answers (2)

alpha
alpha

Reputation: 323

One way to view it is that the problem asks for the intersection of 2 languages: one containing an even number of zeroes and another having the number of ones divisible by 3. A way to approach this is to make DFAs for both the languages and then make another DFA which keeps track of the pair of states in each DFA when an input symbol is read.

I have used 'e' and 'o' to denote that the number of zeroes is even or odd respectively. The second digit in each of the states defines the remainder obtained by dividing the number of ones by 3.

Upvotes: 1

Harald
Harald

Reputation: 5113

You need states which record the divisibility by 2 and by 3, which means you need 6 states. Just call them 0|0, 1|0, 0|1, 1|1, 0|2, 1|2. The first digit tells you that when you reach the state, you have an even or odd number of zeros, the 2nd digit tells you that when you reach the state, you have a number of 1s that, when divided by 3, give the given modulus.

Your state diagram contains:

0|x   --0-->   1|x
1|x   --0-->   0|x 
y|0   --1-->   y|1
y|1   --1-->   y|2
y|2   --1-->   y|0

The start state is 0|0, which is also the only stop state.

The important bit to understand is that each state records the the modulus of the number of zeros or ones read when divided by 2, respectively 3. The 0|0 is then modulus 0 in both cases, which is the accepting criteria. This all works, because the number of different states to keep track of is finite. The name DFA tells us already that it would not work for an infinite number of states to track.

Upvotes: 1

Related Questions