DFA & NFA (Finite Automata)

What is a finite automaton?

A finite automaton is a tiny abstract machine. It reads an input string one symbol at a time and moves between a finite number of states. It has no other memory — the current state is everything it remembers.

Analogy: a turnstile. States: locked, unlocked. Insert a coin → unlocked. Push → locked again. It never needs to remember more than that.

A finite automaton is defined by five things (Q, Σ, δ, q₀, F):

In the 3D model, states are spheres, accepting states have a green halo, and the arrow labelled “start” points to q₀.

DFA — deterministic

For every state and every symbol there is exactly one next state. Running a DFA is simple: start at q₀, follow one arrow per symbol, and check whether you end in F.

Example — strings ending in 01:

Example — binary numbers divisible by 3: the state is the remainder so far. Reading bit b turns remainder r into (2r + b) mod 3 — a DFA can do arithmetic!

NFA — nondeterministic

An NFA may have zero, one or several arrows for the same symbol (and sometimes ε-arrows that use no input). It accepts if at least one possible path ends in an accepting state.

To run an NFA, keep the set of all states it could be in — that’s what the model shows when several spheres glow at once.

NFAs are often smaller and easier to design (“guess where the pattern starts”), but they’re not more powerful.

DFA = NFA in power

Any NFA can be converted into an equivalent DFA with the subset construction: each DFA state represents a set of NFA states. In the worst case a k-state NFA needs 2ᵏ DFA states. The languages they recognise are exactly the regular languages — the same ones described by regular expressions.

Code

def run_dfa(delta, start, accept, s):
    state = start
    for c in s:
        state = delta[state][c]
    return state in accept

ends01 = {"q0": {"0": "q1", "1": "q0"},
          "q1": {"0": "q1", "1": "q2"},
          "q2": {"0": "q1", "1": "q0"}}
print(run_dfa(ends01, "q0", {"q2"}, "11001"))   # True

def run_nfa(delta, start, accept, s):
    states = {start}
    for c in s:
        states = {t for q in states for t in delta.get(q, {}).get(c, [])}
    return bool(states & accept)

nfa01 = {"q0": {"0": ["q0", "q1"], "1": ["q0"]}, "q1": {"1": ["q2"]}}
print(run_nfa(nfa01, "q0", {"q2"}, "1101"))     # True

What finite automata can’t do

They have only finitely many states, so they can’t count without limit. Languages like aⁿbⁿ, balanced parentheses or palindromes are not regular. (The pumping lemma is the standard proof tool.) For those you need a pushdown automaton.

Where are they used?

Lexical analysers in compilers (recognising keywords and numbers), regex engines, network protocols, vending machines, traffic lights, game AI and text search.

Common mistakes

• Forgetting a transition in a DFA — every state needs one arrow per symbol (add a “dead” state if needed).
• Deciding acceptance in the middle of the string — only the final state counts.
• Thinking NFAs are more powerful than DFAs.