DFA Example 1

For Complete YouTube Video: Click Here

In this class, We discuss DFA Example 1.

The reader should have prior knowledge of examples to understand finite automata class. Click here.

We discussed DFA, and the intuition provided in the previous class examples will help a lot here.

Q1) Design a DFA that accepts strings that contain the last two characters one’s.

In our first example, we go step by step.

From the question, we understand we need to check two consecutive one’s from the string.

Suppose the two consecutive ones are the end of the string. Then accepted.

Example String: 11

String 11 should be accepted because the last two characters in the string are one’s.

The below diagram shows the logic to construct DFA.

We consider three states. q1,q2, and qf, respectively.

Whenever we see input one on state q1, we move to state q2.

When we see input one on state q2, we move to state qf.

From this, we understand whenever we see two consecutive one’s we are moving to state qf.

The state qf is considered the final state.

Remember, the two consecutive ones should be the last two characters. We think about the remaining logic.

Example String: 1011

In the above input string, we take the first input character one and move to state q2.

On state q2, we encountered the input zero. Now on seeing input zero, where do we have to move?

We move to state q1; why?

Reason: we have to see two consecutive ones. But after looking at one, we encountered zero, so two consecutive one’s logic is missing.

So we need to go back to state q1 and again check for two consecutive ones for the next coming input characters.

Hint: we explained in first class. We do not have memory.

So we have to think of the logic accordingly.

The logic is shown below diagram.

Example string: 1111

The above string will take the first two input characters 11 and move to the final state qf.

On state qf the next input character is 1. so we stay on the state qf.

Why do we stay on the state qf?

After two consecutive one’s we saw the input character 1. Still, the last two characters are one’s.

So we stay on state qf if the input character seen on state qf is 1.

The below diagram shows the Updated DFA.

Example String: 110011

The above string takes the first two input characters and moves to the state qf.

On state qf the input character seen is zero.

On state qf if we encounter input character zero. We move to state q1.because the last two characters are not 11.

We have to check the logic for two consecutive ones again. So we move to state q1.

After moving to state q1 again, we encounter the input character 0.

We stay on state q1 by seeing the input character zero. Because our logic is to find two consecutive ones, so we don’t take a step.