Question

-

Give state diagram of DFA recognizing L={w | w is 0,1-string, and contains 3k 0s and 2m 1s for some integers k and m at least 0}. For examples, 0010111 is in L, but 010011 is not in L. The first string contains 3 0s and 4=2x2 1s, but the second string has an odd number of 1s.

Answer 1

DFA: In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

When the string is passed to the DFA and ends on the final state, denoted by two circles, the string is accepted by L and when string ends in a non-final state the string is not accepted.

So when we move from q2 or q4 to left, we make it 3k+3 i.e. 3(k+1) hence mutliple of 3.

Similary when we move from top to down we increase the count of number of 1's by 1 and hence it becomes 2m+1 and when we go from down to top number of 1's increase by 1 resulting into 2m+2 i.e. 2(m+1) hence multiple of 2.

So, when we reach to q0, we have number of 1's in form of 2m and number 0's in form of 3k.

Let's see use the first exmaple given in question:

L₁ = 0010111

Transition Character

Step 1: q₀ -> q₁ 0

Step 2: q₁ -> q₂ 0

Step 3: q₂ -> q₅ 1

Step 4: q₅ -> q₃ 0

Step 5: q₃ -> q₀ 1

Step 6: q₀ -> q₃ 1

Step 7: q₃ -> q₀ 1

Since q0 is final state hence the string L₁ i.e. 0010111 is accepted.

Now let's have a look at second example
L₂ = 010011

Step 1: q0 -> q1 0

Step 2: q1 -> q4 1

Step 3: q4 -> q5 0

Step 4: q5 -> q3 0

Step 5: q3 -> q0 1

Step 6: q0 -> q3 1

Here the string ends on state q3, which is not the final state, hence this string will not be accepted and is not in the form of 'w' as mentioned in above.

Thank You and Have a good day,