DFA vs NFA

Epsilon (ε) Transitions Explained

An epsilon (ε) transition is a transition in an NFA that moves from one state to another without consuming any input symbol. It represents a spontaneous state change — the machine can take the transition “for free.” Epsilon transitions do not exist in DFAs.

Example: NFA-ε accepting strings of the form aⁿ or bⁿ (only a’s or only b’s)

States: Q = {q0, q1, q2}     Start: q0     Accept: {q1, q2}

Transition Table (NFA-ε):
┌────────┬──────────┬──────────┬──────────┐
│ State  │ Input: a │ Input: b │  ε       │
├────────┼──────────┼──────────┼──────────┤
│  q0   │    ∅     │    ∅     │ {q1, q2} │
│  q1   │  {q1}   │    ∅     │    ∅     │
│  q2   │    ∅     │  {q2}   │    ∅     │
└────────┴──────────┴──────────┴──────────┘

State diagram:
         ε ──→ (q1) ─a─→ (q1) [self-loop]
              ↗
  ──→ (q0)
              ↘
         ε ──→ (q2) ─b─→ (q2) [self-loop]

Epsilon Closure (ε-closure)

The ε-closure of a state q is the set of all states reachable from q by following zero or more ε-transitions. It is essential for simulating NFA-ε and for converting NFA-ε to DFA.

For the example above:
  ε-closure(q0) = {q0, q1, q2}  ← q0 can reach q1 and q2 via ε
  ε-closure(q1) = {q1}           ← q1 has no ε-transitions
  ε-closure(q2) = {q2}           ← q2 has no ε-transitions

Processing "aaa":
  Start: ε-closure(q0) = {q0, q1, q2}
  Read a: δ({q0,q1,q2}, a) → from q1 only → {q1} → ε-closure = {q1}
  Read a: δ({q1}, a) → {q1} → ε-closure = {q1}
  Read a: δ({q1}, a) → {q1} → ε-closure = {q1}
  q1 ∈ F ✓ ACCEPT

Processing "ab":
  Start: ε-closure(q0) = {q0, q1, q2}
  Read a: → {q1}
  Read b: δ({q1}, b) → ∅ → ε-closure = ∅
  No accept state reachable ✗ REJECT

Worked Example: Processing the Same String in DFA and NFA

The clearest way to see the difference is to process the same input string through both an equivalent DFA and NFA step by step. Below, both automata accept the language of strings over {0, 1} that end in ‘1’.

Step  Symbol  Current → Next
  1     0      q0  →  q0
  2     1      q0  →  q1
  3     0      q1  →  q0
  4     1      q0  →  q1

Final state: q1 ∈ F  ✓ ACCEPT

At each step: exactly ONE next state.
No choices, no branching.
One linear path through the machine.

Step  Symbol  Active states → Next states
  1     0      {q0}  →  {q0}
  2     1      {q0}  →  {q0, q1}
  3     0      {q0,q1} → {q0}
               (q1 has no '0' transition)
  4     1      {q0}  →  {q0, q1}

Final states: {q0, q1}
q1 ∈ F  ✓ ACCEPT (at least one accept state)

At each step: a SET of active states.
Multiple parallel paths tracked simultaneously.

DFA vs NFA: 12 Critical Differences

NFA to DFA Conversion: Subset Construction Method

Every NFA can be converted to an equivalent DFA that accepts exactly the same language. The algorithm is called subset construction (or the powerset construction). The core idea: each state of the DFA corresponds to a set of NFA states that the NFA could be in simultaneously.

Step-by-Step Conversion: Worked Example

Given NFA: Accepts strings over {a, b} containing ‘ab’ as a substring.

NFA States: Q = {q0, q1, q2}
Alphabet: Σ = {a, b}
Start: q0     Accept: {q2}

NFA Transition Table:
┌────────┬───────────┬──────────┐
│ State  │    a      │    b     │
├────────┼───────────┼──────────┤
│  q0   │ {q0, q1}  │  {q0}   │
│  q1   │    ∅      │  {q2}   │
│  q2   │  {q2}    │  {q2}   │
└────────┴───────────┴──────────┘

Step 1: Start with the ε-closure of the NFA start state. (No ε-transitions here, so ε-closure(q0) = {q0}.)

DFA start state = A = {q0}

Step 2: For each DFA state (set of NFA states), compute transitions on each input symbol by applying δ to every NFA state in the set and taking the union.

DFA State    On 'a'                          On 'b'
─────────────────────────────────────────────────────
A = {q0}     δ(q0,a) = {q0,q1} → B          δ(q0,b) = {q0} → A
B = {q0,q1}  δ(q0,a)∪δ(q1,a) = {q0,q1}∪∅   δ(q0,b)∪δ(q1,b) = {q0}∪{q2}
             = {q0,q1} → B                  = {q0,q2} → C
C = {q0,q2}  δ(q0,a)∪δ(q2,a) = {q0,q1}∪{q2} δ(q0,b)∪δ(q2,b) = {q0}∪{q2}
             = {q0,q1,q2} → D               = {q0,q2} → C
D={q0,q1,q2} δ(q0,a)∪δ(q1,a)∪δ(q2,a)      δ(q0,b)∪δ(q1,b)∪δ(q2,b)
             = {q0,q1}∪∅∪{q2} = {q0,q1,q2} = {q0}∪{q2}∪{q2}
             → D                             = {q0,q2} → C

Step 3: Mark accept states. Any DFA state whose NFA subset contains an NFA accept state (q2) is a DFA accept state.

Final DFA:
┌──────────────────┬──────┬──────┬──────────┐
│ DFA State        │  a   │  b   │ Accept?  │
├──────────────────┼──────┼──────┼──────────┤
│ A = {q0}    →   │  B   │  A   │   No     │
│ B = {q0,q1} →   │  B   │  C   │   No     │
│ C = {q0,q2} →   │  D   │  C   │  YES ✓   │
│ D={q0,q1,q2}→   │  D   │  C   │  YES ✓   │
└──────────────────┴──────┴──────┴──────────┘

DFA has 4 states. NFA had 3 states.
(State explosion avoided here — worst case would be 2³ = 8 states)

Step 4: Verify. Processing “ab” in the DFA: A →a→ B →b→ C (accept ✓). Processing “ba”: A →b→ A →a→ B (reject ✓, ‘ba’ doesn’t contain ‘ab’). The converted DFA is correct.

General Subset Construction Algorithm

Python Implementation

class DFA:
    def __init__(self, transitions,
                 start_state, accept_states):
        self.transitions = transitions
        self.start = start_state
        self.accept = accept_states

    def process(self, input_string):
        state = self.start
        for char in input_string:
            state = self.transitions.get(
                (state, char))
            if state is None:
                return False  # dead state
        return state in self.accept

# DFA accepting strings ending in '1'
dfa = DFA(
    transitions={
        ('q0','0'):'q0', ('q0','1'):'q1',
        ('q1','0'):'q0', ('q1','1'):'q1'
    },
    start_state='q0',
    accept_states={'q1'}
)
print(dfa.process('101'))  # True
print(dfa.process('110'))  # False

class NFA:
    def __init__(self, transitions,
                 start_state, accept_states):
        self.transitions = transitions
        self.start = start_state
        self.accept = accept_states

    def process(self, input_string):
        # Track SET of active states
        active = {self.start}
        for char in input_string:
            next_states = set()
            for state in active:
                next_states.update(
                    self.transitions.get(
                        (state, char), set()))
            active = next_states
        # Accept if any active state is final
        return bool(active & self.accept)

# NFA accepting strings containing 'ab'
nfa = NFA(
    transitions={
        ('q0','a'):{'q0','q1'},
        ('q0','b'):{'q0'},
        ('q1','b'):{'q2'},
        ('q2','a'):{'q2'},
        ('q2','b'):{'q2'}
    },
    start_state='q0',
    accept_states={'q2'}
)
print(nfa.process('ab'))   # True
print(nfa.process('bab'))  # True
print(nfa.process('ba'))   # False

Related Topics Worth Exploring