NFA Examples 1
For Complete YouTube Video: Click Here
In this class, We discuss NFA Examples 1.
The reader should have prior knowledge of how NFA executes. Click here.
First Example: Design NFA that accepts string 1100 only.
The input symbols are Σ {0,1}.
Example: The string 1100 should be accepted.
The string 11000 is not be accepted because, after 1100, we have another zero.
The initial state is q0.
On the state q0, when we see the input character one, we move to state q1.
On the state q0, we did not mention the input symbol zero.
When we encounter the input symbol zero on state q0, the NFA will be dead.
Suppose the first input character is zero no need to check the remaining logic because we lost the logic required.
If we do not mention the input symbol, the NFA is going to die. So writing logic in NFA is easy.
The same logic we did in our DFA examples. We mentioned a dead state.
The logic we mentioned in NFA is easy. We just leave the input symbol on the state.
Similarly, on state q1, if we see the input symbol one, we move to state q2.
On state q2, if we encounter symbol zero, we move to state q3.
On state q3, if we see the input symbol zero, we move to state q4.
We consider state q4 as the final state.
On state q4, we do not mention any transition. Because if we see any transition, we need to stop the execution of NFA.
Second Example: Design NFA That accepts strings having 1100 as a substring.
The input symbols are Σ {0,1}.
First, we construct the base logic.
Whenever we find consecutive 1100, we need to move to the final state.
We start from state q0 and move to state q4 when we encounter consecutive 1100.
On state q0, we mention one more transition. If the input is zero or one, move to state q0.
Now on state q0, if the input is one, we move to state q0 and q1.
One machine is going to take the next input character on q0.
Another machine is going to take the next character on q1.
One machine is going to check the logic again from the beginning.
Other machines are moving one step on the base logic.
Because our logic is to identify sub-string 1100, we are taking two transitions.
After reaching the final state, we stay on the final state for further inputs.
Once we identify sub-string 1100, we can stay in the final state.
Similarly, we can write NFA for language accepting the last four symbols as 1100.
The below diagram shows the NFA for language accepting the last four symbols 1100.
