DFA Examples on Counting

For Complete YouTube Video: Click Here

In this class, We discuss DFA Examples on Counting.

The reader should have prior knowledge of DFA examples. Click here.

First Question: Design DFA that accepts strings with an even number of zeros.

The input symbols are Σ={0,1}.

Example Strings: 01011  

The string 01011 is accepted because two zeros are present.

Point to understand: The zeros need not be consecutive.

The previous examples are dependent on consecutive character-identifying logic.

In the example, we are not bothered about ones. so we stay in the same state when encountering the input one.

The below diagram shows the DFA accepting strings containing even zeros.

On the state q0, if we see the input character zero, we move to state q1.

When we see the input character zero on state q1, we move to state q0.

For one zero, we move to state q1. For the other zero, we move to state q0.

Whenever we find an even number of zeros, we are in the state q0.

So we make q0 the final state.

We are not bothered about ones; we stay in the same state if we see input 1.

Second Question: Design DFA that accepts strings having the number of zeros multiples of 3.

The input symbols are Σ={0,1}.

In the above example, we counted the zeros multiples of 2.

We use the same logic with a step extension.

The below diagram shows the complete DFA.

From state q0, we take one step when we see the input symbol zero.

One more step from state q1 when we see input symbol zero.

From the state q2, if we encounter the input symbol zero, we move to state q0.

We are counting the zeros. For the count of three zeros, we reach the state q0.

The final state is considered as q0.