Design a non-deterministic finite automaton (NFA) over the alphabet Σ = {0, 1}…
2025
Design a non-deterministic finite automaton (NFA) over the alphabet Σ = {0, 1} that accepts the language:
L = { w | w ends with 01 or 10 }
Once the NFA is constructed, convert it into an equivalent Deterministic Finite Automaton (DFA) using the subset construction method. Clearly label the states and transitions in your DFA.
Show answer & explanation
The language is L = {w ∣ w ends with 01 or 10} over alphabet Σ={0,1}.
Thus, a string is accepted only if its last two symbols are different.
NFA Construction
Let the NFA be M=(Q,Σ,δ,q0,F)
Q = {q0, q1, q2, q3}
Σ = {0,1}
Start state = q0
Final state = {q3}
Explanation
State q0 scans the string.
If 0 appears, the NFA guesses that pattern 01 may occur → moves to q1.
If 1 appears, it guesses 10 → moves to q2.
Transition q1 →1→ q3 completes 01.
Transition q2 →0→ q3 completes 10.
q3 is the accepting state since the string ends with 01 or 10.
Subset Construction (NFA → DFA)
Start state = {q0}
DFA State | Input 0 | Input 1 |
|---|---|---|
{q0} | {q0,q1} | {q0,q2} |
{q0,q1} | {q0,q1} | {q0,q2,q3} |
{q0,q2} | {q0,q1,q3} | {q0,q2} |
{q0,q2,q3} | {q0,q1,q3} | {q0,q2} |
{q0,q1,q3} | {q0,q1} | {q0,q2,q3} |
Accepting DFA states:
Any subset containing q3, i.e. {q0,q2,q3} and {q0,q1,q3}.
Conclusion
Using the subset construction method, the nondeterministic choices of the NFA are replaced by deterministic state sets. The resulting DFA correctly accepts all binary strings whose last two symbols are 01 or 10, making it equivalent to the original NFA.