NFA Example: Substring Recognition
You'll learn how to build an NFA that recognizes any string containing a particular substring by using nondeterminism to "guess" where the pattern begins.
The Core Idea
Imagine you're scanning text to find the word "cat" anywhere inside it. With a DFA, you'd need to carefully track partial matches and handle resets when they fail—complicated! An NFA can simply guess when the substring starts and follow that path. If the guess is right and the pattern completes, the string is accepted. If wrong, other parallel paths might succeed.
This is where nondeterminism shines: instead of meticulously managing all possibilities, you create multiple choices and let the NFA explore them simultaneously.
Example: Recognizing Strings Containing "101"
Let's design an NFA that accepts any string containing "101" as a substring over alphabet {0, 1}.
Strategy:
- State q₀ (start): Guess when "101" begins. Stay here on any input, but also nondeterministically transition to q₁ on seeing '1'
- State q₁: Just saw '1', expecting '0' next
- State q₂: Just saw "10", expecting '1' next
- State q₃ (accept): Saw complete "101", stay here forever (anything after is fine)
Transitions:
- q₀ → q₀ on {0, 1} (keep waiting/guessing)
- q₀ → q₁ on 1 (nondeterministic guess: pattern starts here!)
- q₁ → q₂ on 0
- q₂ → q₃ on 1
- q₃ → q₃ on {0, 1} (once found, always accept)
The NFA "stays alert" in q₀ until it guesses correctly. For input "00101", one path stays in q₀ while another branches to track "101" starting at position 2, eventually reaching q₃.
Key Takeaway: NFAs elegantly recognize substring patterns by nondeterministically guessing where the pattern starts, avoiding the complex state tracking required in DFAs.