NFA Practice Examples

For Complete YouTube Video: Click Here

In this class, We discuss NFA Practice Examples.

The reader should have prior knowledge of NFA Execution. Click here.

First Example: Design an NFA that accepts strings having the last two characters 00 or 11.

The input symbols are Σ {0,1}.

The given condition is last two characters should be 00 or 11.

We discuss how to write logic for or condition in our DFA examples.

NFA can move to multiple states. One machine will check the logic from one state, and the other machine will check the logic from another state.

We use a combination of the above two conditions to design our NFA.

On state q0, when we see input symbol zero, we move to state q0 and q1.

On the state q0, when we encounter the input one, we move to state q0 and q3.

We are moving in one direction two find the base logic of two consecutive zeros. And another direction to find consecutive ones.

On state q1, when we see input character zero, we move to state q2.

The state q2 is considered one of the final states.

On state q2, we did not mention any transition because we need to find the last two characters’ zeros.

So after finding two consecutive zeros, we still have input characters we need our NFA to die.

Similarly, on state q3, when we encounter input one, we move to state q4.

The state q4 is considered the final state.

On the state q4, we don’t mention any transition because we need to check the last two characters are ones.

The below diagram shows the complete NFA.

Second Example: Design NFA that accepts strings containing 1100 or 1010 as a substring.

The input symbols are Σ {0,1}.

In both substrings, the first symbol is one. So we start logic with checking one.

After the first character, we need to differentiate both strings using one and zero.

On the state q0, if we see the input symbol one, we move to state q0 and q1.

On the state q1, if we encounter the input symbol one, we move to state q2. On input symbol zero, we move to state q5.

One way is identifying the string 1100, and the other way is identifying 1010.

The states q4 and q7 are considered final states.

If we see any input symbol on the final states, we stay on the final state because we need to identify the sub-string.

Once we moved to the final state, we found the sub-string required. So we stay in the final state.