Non-deterministic Finite Automata (NFA)

What is an NFA?

Non-deterministic Finite Automaton (NFA) is a theoretical machine similar to DFA, but with more flexibility in transitions. It’s called “non-deterministic” because from any state, for any input symbol, there can be zero, one, or multiple next states. The NFA can also make transitions without reading any input (ε-transitions).

Formal Definition

An NFA is a 5-tuple M = (Q, Σ, δ, q₀, F) where:

• Q: Finite set of states
• Σ: Finite input alphabet
• δ: Transition function δ: Q × (Σ ∪ {ε}) → P(Q)
• q₀: Start state (q₀ ∈ Q)
• F: Set of accepting/final states (F ⊆ Q)

Note: P(Q) is the power set of Q (all possible subsets)

Simple Analogy

Think of NFA like a maze with multiple paths:

• DFA: At each junction, only one path to take (deterministic)
• NFA: At each junction, you can:
  • Take multiple paths at once (non-determinism)
  • Teleport without moving (ε-transitions)
  • Have no path available (dead end)

Magic: If any path leads to an exit (accept state), you succeed!

Key Differences: DFA vs NFA

Components of NFA

1. Multiple Transitions

Same (state, symbol) can lead to different states

Example:
δ(q₀, a) = {q₁, q₂}

From q₀ on input 'a', NFA can go to either q₁ OR q₂

2. ε-Transitions (Epsilon Moves)

Move between states without consuming input

Example:
δ(q₀, ε) = {q₁, q₂}

From q₀, NFA can spontaneously move to q₁ or q₂

3. Missing Transitions

Some (state, symbol) combinations have no transitions

Example:
δ(q₁, b) = ∅ (empty set)

From q₁ on input 'b', nowhere to go (dead end)

How NFA Works

Acceptance Mechanism

An NFA accepts a string w if:

There exists at least one path from q₀ to any state in F that consumes w

Key Idea: NFA explores all possible paths simultaneously (conceptually)

Execution Process

1. Start: Begin in state q₀
2. Branch: At each step, pursue all possible transitions
3. ε-closure: Include all states reachable via ε-transitions
4. Parallel paths: Track multiple current states simultaneously
5. Accept: If any path ends in F → ACCEPT
6. Reject: If all paths fail → REJECT

Example Trace

NFA for strings containing “01”:

States: {q₀, q₁, q₂}
Σ = {0, 1}
F = {q₂}

Transitions:
δ(q₀, 0) = {q₀, q₁}  (stay or move)
δ(q₀, 1) = {q₀}       (stay)
δ(q₁, 1) = {q₂}       (found "01"!)
δ(q₂, 0) = {q₂}       (stay in accept)
δ(q₂, 1) = {q₂}       (stay in accept)

Input: “101”

Step 0: {q₀}
Step 1 (read '1'): {q₀}
Step 2 (read '0'): {q₀, q₁}
Step 3 (read '1'): {q₀} ∪ {q₂} = {q₀, q₂}

q₂ ∈ F → ACCEPT ✓

Even though one path stays at q₀, another path reached q₂!

Examples of NFAs

Example 1: Strings Ending with “01”

Language: L = {w | w ends with “01”}

NFA:

State Diagram:
      0,1      0       1
→(q₀)━━━━→(q₁)━━━→((q₂))
  ↺

Transitions:

• δ(q₀, 0) = {q₀, q₁} (guess if this is the final ‘0’)
• δ(q₀, 1) = {q₀} (definitely not the ending)
• δ(q₁, 1) = {q₂} (found ending “01”!)
• q₂ has no outgoing transitions (if we reach here, we’re done)

Key Insight: We “guess” when the ending “01” begins!

Example 2: Contains Substring “ab”

Language: L = {w | w contains “ab”}

NFA:

      a,b      a       b
→(q₀)━━━━→(q₁)━━━→((q₂))
  ↺                    ↺ a,b

Transitions:

• δ(q₀, a) = {q₀, q₁} (could be start of “ab”)
• δ(q₀, b) = {q₀} (not “ab” yet)
• δ(q₁, b) = {q₂} (found “ab”!)
• δ(q₂, a) = {q₂} (stay once found)
• δ(q₂, b) = {q₂} (stay once found)

Much simpler than DFA version!

Example 3: Strings of Length 2 or 3

Language: L = {w | |w| = 2 or |w| = 3}

NFA:

      0,1      0,1
→(q₀)━━━→(q₁)━━━→((q₂))
                   ↓ 0,1
                 ((q₃))

Simple: Count 2 or 3 transitions, accept at both!

Example 4: Strings with ‘a’ at 2nd or 3rd Position from End

Language: L = {w | 2nd or 3rd symbol from end is ‘a’}

NFA:

      a,b         a       a,b     a,b
→(q₀)━━━━━→(q₁)━━━→((q₂))━━━→((q₃))
  ↺

Transitions:

• δ(q₀, a) = {q₀, q₁} (guess if this is the key ‘a’)
• δ(q₀, b) = {q₀}
• δ(q₁, a) = {q₂}
• δ(q₁, b) = {q₂}
• δ(q₂, a) = {q₃}
• δ(q₂, b) = {q₃}

Key: Guess when we’re 2-3 positions from end!

Example 5: (a|b)*a (Ending with ‘a’)

NFA with ε-transition:

         ε
    ┌────────┐
    ↓        │
→(q₀)  (q₁)  ((q₂))
    │   ↑ a   ↑
    └──→ └──→┘
      a,b  a

Transitions:

• δ(q₀, ε) = {q₁} (ε-transition to start)
• δ(q₁, a) = {q₁, q₂} (process ‘a’, maybe ending)
• δ(q₁, b) = {q₁} (process ‘b’)

Example 6: Strings Where 3rd Symbol from End is ‘1’

Language: L = {w | 3rd symbol from end is ‘1’}

NFA:

      0,1      1       0,1     0,1
→(q₀)━━━━→(q₁)━━━→((q₂))━━━→((q₃))
  ↺

Strategy: Guess when we’re 3 positions from end, check for ‘1’

DFA would need 2³ = 8 states to remember last 3 symbols! NFA only needs 4 states with non-determinism!

ε-Transitions (Epsilon Moves)

What are ε-Transitions?

Definition: Transitions that occur without consuming input

Notation: δ(q, ε) = {p, r, …}

Meaning: From state q, can spontaneously move to p or r

Why Use ε-Transitions?

1. Simplify construction: Easier to combine NFAs
2. Express alternatives: Model “choice” between paths
3. Regex conversion: Natural from regular expressions

ε-Closure

Definition: ε-closure(q) = set of all states reachable from q using only ε-transitions

Algorithm:

ε-closure(q):
1. result = {q}
2. For each state p reachable from q via ε:
   result = result ∪ ε-closure(p)
3. Return result

Example:

δ(q₀, ε) = {q₁, q₂}
δ(q₁, ε) = {q₃}
δ(q₂, ε) = ∅
δ(q₃, ε) = ∅

ε-closure(q₀) = {q₀, q₁, q₂, q₃}

Example with ε-Transitions: (a|b)*

NFA:

         ε       a        ε
    ┌─────→(q₁)───→(q₂)────┐
    │                       ↓
→((q₀))                    ((q₅))
    │                       ↑
    └─────→(q₃)───→(q₄)────┘
         ε       b        ε

Transitions:

• δ(q₀, ε) = {q₁, q₃} (choose a-path or b-path)
• δ(q₁, a) = {q₂}
• δ(q₂, ε) = {q₅}
• δ(q₃, b) = {q₄}
• δ(q₄, ε) = {q₅}
• δ(q₅, ε) = {q₁, q₃} (loop back for repetition)

Accepts: All strings over {a, b}

NFA Acceptance Algorithm

Method 1: Parallel Simulation

def nfa_accepts(nfa, input_string):
    current_states = epsilon_closure({q₀})

    for symbol in input_string:
        next_states = set()
        for state in current_states:
            next_states |= δ(state, symbol)
        current_states = epsilon_closure(next_states)

    return any(state in F for state in current_states)

Time Complexity: O(n × m²) where n = input length, m = number of states

Method 2: Backtracking

def nfa_accepts_backtrack(nfa, state, remaining_input):
    if not remaining_input:
        return state in F

    # Try ε-transitions first
    for next_state in δ(state, ε):
        if nfa_accepts_backtrack(nfa, next_state, remaining_input):
            return True

    # Try consuming input
    symbol = remaining_input[0]
    for next_state in δ(state, symbol):
        if nfa_accepts_backtrack(nfa, next_state, remaining_input[1:]):
            return True

    return False

Advantages of NFA over DFA

1. Fewer States

Example: 3rd symbol from end is ‘a’

• NFA: 4 states (with non-determinism)
• DFA: 8 states (must remember all possibilities)

2. Easier to Design

Substring problems are natural in NFA:

• Guess when pattern starts
• Verify pattern
• Accept if found

3. Direct from Regex

Thompson’s Construction naturally produces NFAs with ε-transitions

4. Modular Construction

Easy to combine:

• Union: Add ε-transitions from new start
• Concatenation: Connect with ε-transitions
• Star: Add loops with ε-transitions

5. Conceptually Simpler

Express “or” naturally:

• “Path 1 OR Path 2” → multiple transitions
• “Accept if any path works” → non-determinism

Disadvantages of NFA

1. Slower Recognition

DFA: O(n) - single path NFA: O(n × m²) - multiple paths

2. Complex Implementation

Need to track:

• Multiple current states
• ε-closures
• Parallel paths

3. More Memory at Runtime

Must store: Set of currently active states

4. Non-deterministic Choice

Ambiguity: Which path to take? (Requires backtracking or parallel simulation)

Equivalence: NFA and DFA

Fundamental Theorem

Theorem: For every NFA, there exists an equivalent DFA.

L(NFA) = L(DFA)

Both accept exactly the same language!

Proof Idea: Subset construction (power set method)

Conversion Complexity

NFA with n states → DFA with up to 2ⁿ states

Example:

• NFA: 4 states
• DFA: Up to 2⁴ = 16 states (worst case)
• Often fewer in practice

Expressive Power

NFA = DFA = Regular Languages

All three are equivalent:

1. Languages accepted by DFA
2. Languages accepted by NFA
3. Languages described by regular expressions

Designing NFAs

Strategy 1: Guess-and-Verify

Pattern: “Contains substring”

1. Guess when pattern starts (multiple transitions)
2. Verify pattern
3. Stay in accept state once found

Strategy 2: Position from End

Pattern: “k-th symbol from end is ‘a’”

1. Guess when we’re k positions from end
2. Verify next k-1 symbols exist
3. Accept

Strategy 3: Multiple Conditions (OR)

Pattern: “Ends with ‘01’ OR ends with ‘10’”

1. Branch with ε-transitions
2. Each branch handles one condition
3. Accept if any branch succeeds

Strategy 4: Regular Expression

Pattern: Given regex r

1. Apply Thompson’s Construction
2. Automatically get NFA with ε-transitions

Important Properties

1. Closure Properties

NFAs (like DFAs) are closed under:

• ✓ Union
• ✓ Concatenation
• ✓ Kleene Star
• ✓ Intersection
• ✓ Complement (via DFA conversion)

2. Decidability

For NFAs, we can decide:

• ✓ Membership: Is w ∈ L(NFA)?
• ✓ Emptiness: Is L(NFA) = ∅?
• ✓ Finiteness: Is L(NFA) finite?
• ✓ Equivalence: L(NFA₁) = L(NFA₂)?

3. Minimization

NFAs don’t have unique minimal form (unlike DFAs)

• Convert to DFA
• Minimize DFA
• Optionally convert back to NFA

Practical Applications

1. Regular Expression Engines

Python re module, grep, sed
Internal representation: NFA

2. Lexical Analyzers

Flex, Lex: Generate code from regex
Use NFA internally for flexibility

3. Pattern Matching

Text editors (vim, emacs)
Search functionality

4. Network Protocol Validation

Intrusion detection systems
Packet filtering

5. DNA Sequence Matching

Bioinformatics tools
Pattern searching in genomes

Important Exam Points

1. ✓ NFA = Non-deterministic Finite Automaton
2. ✓ Multiple transitions: δ(q, a) can be {q₁, q₂, …}
3. ✓ ε-transitions: Move without consuming input
4. ✓ Acceptance: If any path leads to accept state
5. ✓ ε-closure(q): All states reachable via ε-transitions
6. ✓ NFA = DFA in power (equivalent languages)
7. ✓ Conversion: NFA → DFA via subset construction
8. ✓ Size: NFA often smaller, DFA may need 2ⁿ states
9. ✓ Speed: DFA faster O(n), NFA slower O(n·m²)
10. ✓ Design: NFA easier for patterns, especially with “guess”

Common Mistakes to Avoid

✗ Mistake 1: NFA must have exactly one transition per (state, symbol)
✓ Correct: NFA can have 0, 1, or many transitions

✗ Mistake 2: NFA accepts only if all paths accept
✓ Correct: NFA accepts if any path accepts

✗ Mistake 3: DFA can have ε-transitions
✓ Correct: Only NFA can have ε-transitions

✗ Mistake 4: NFA is more powerful than DFA
✓ Correct: NFA and DFA are equivalent in power

✗ Mistake 5: δ(q, a) returns a single state in NFA
✓ Correct: δ(q, a) returns a set of states

✗ Mistake 6: NFA is always smaller than equivalent DFA
✓ Correct: Usually smaller, but conversion can exponentially increase size

Practice Questions

Q1: Can an NFA have multiple start states?

Answer: No, only one start state q₀. But can use ε-transitions to simulate multiple starts.

Q2: What is ε-closure({q₀, q₁})?

Answer: Union of ε-closure(q₀) and ε-closure(q₁) - all states reachable from either via ε-transitions.

Q3: Design NFA for strings ending with “abc”.

Answer:

      a,b,c    a       b       c
→(q₀)━━━━━→(q₁)━━━→(q₂)━━━→((q₃))
  ↺

Q4: How many states in worst-case DFA from n-state NFA?

Answer: 2ⁿ states (exponential blow-up possible)

Q5: Can NFA recognize non-regular languages?

Answer: No, NFA = DFA in power, both recognize only regular languages.

Q6: What does δ(q, ε) mean?

Answer: Set of states reachable from q without consuming input.

Q7: Is every DFA also an NFA?

Answer: Yes, DFA is a special case of NFA (deterministic = one transition per (state, symbol)).

Q8: When would you prefer NFA over DFA?

Answer: When designing automata - NFA is simpler for patterns like “contains substring” or “k-th from end”.

Summary

• NFA = Non-deterministic Finite Automaton
• Multiple transitions: 0, 1, or many per (state, symbol)
• ε-transitions: Move without input consumption
• Acceptance: If any path reaches accept state
• Equivalent to DFA: Same expressive power (regular languages)
• Advantages: Fewer states, easier design, direct from regex
• Disadvantages: Slower recognition, complex implementation
• Conversion: NFA → DFA via subset construction (2ⁿ states worst case)
• ε-closure: Key concept for handling ε-transitions
• Applications: Regex engines, lexical analyzers, pattern matching

NFAs provide a more flexible and intuitive model for describing regular languages, especially useful in theoretical constructions and regex-based tools!