Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 68 ยท Computation and Languages

Finite Automata and Regular Languages

Learn DFAs, NFAs and regular languages, simulate state machines in Python, convert NFAs to DFAs, and see how regular expressions connect.

A vending machine, a traffic light, a turnstile and the tokenizer in a compiler all work the same way: they have a handful of states, read one input at a time, and move to a new state according to a fixed table. That is a finite automaton, the simplest model of computation. It has no memory beyond "which state am I in right now", yet it can recognize many useful patterns, and it is the engine behind regular expressions.

In this lesson we define the DFA (deterministic finite automaton) and the NFA (nondeterministic one), simulate both in Python, convert an NFA into a DFA with the subset construction, and see how this connects to regular expressions and to the limits of what a finite machine can do. We use strings over an alphabet such as {0, 1}; a language is a set of such strings, and an automaton accepts the strings in its language. See sets if you need a refresher on sets of objects.

A machine with a few states

States A finite list of situations the machine can be in.
Transitions Each symbol moves the machine to a next state.
Accepting Ending in a marked state means yes.
1 / 2

Deterministic finite automata

A DFA consists of:

  • a finite set of states Q,
  • an alphabet ฮฃ of input symbols,
  • a transition function ฮด(state, symbol) โ†’ state, defined for every pair,
  • a start state q0,
  • a set F of accepting states.

To run it, start in q0, read the string one symbol at a time following ฮด, and at the end accept if you are in a state of F. Because every state has exactly one move per symbol, the run is completely determined by the input.

As a first example, here is a DFA over {0, 1} that accepts strings with an even number of 1s. It has two states, "even" and "odd". A 0 keeps the state; a 1 flips it; the start state "even" is the only accepting one.

flowchart LR
    S(["start"]) --> E(("even"))
    E -->|"0"| E
    E -->|"1"| O(("odd"))
    O -->|"0"| O
    O -->|"1"| E

Two states count the 1s modulo 2. Even is the start and accepting state.

A DFA is a short table plus a short loop, so it is easy to simulate. The second machine below accepts the binary strings that end in 01. It needs three states: "no progress", "just saw a 0", and "just saw 01".

Python Simulating DFAs with a transition table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A language is regular if some DFA accepts it. Regular languages are closed under union, intersection, complement and concatenation. Complement is the easiest to see on a DFA: swap accepting and non-accepting states.

Nondeterministic finite automata

An NFA relaxes the rules. From a state, one symbol may lead to several states, or to none. There can also be epsilon moves (ฮต), which change state without reading anything. The machine accepts a string if at least one sequence of choices ends in an accepting state.

You can think of an NFA as "guessing" the right path, or as running all paths at once. Simulating it is easy: keep the set of states you could be in, and update the whole set at each symbol. For ฮต-moves, first expand the set with its ฮต-closure, everything reachable for free.

Nondeterminism often makes a machine much shorter to write. Here is an NFA for "strings that are either (01)* or end in 11". It starts by branching with ฮต into two little machines, one for each alternative. Writing a single DFA for this union takes more thought.

Python Simulating an NFA with epsilon moves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

NFAs look more powerful, but they are not: every NFA can be turned into a DFA that accepts the same language.

The subset construction

The idea behind the conversion is the same as the simulator above. At any moment, the NFA is in some set of states. Make each possible set a state of the DFA. The start state is the ฮต-closure of the NFA's start. On a symbol, the new state is the set of everything reachable from the old set. A set is accepting if it contains an NFA accepting state.

In the worst case this takes 2^n DFA states for n NFA states, though usually only a few sets are actually reachable. Below, the NFA for "ends in 01" has three states. Its sets form a small DFA, and we check that it agrees with a regular expression.

Python Converting an NFA to a DFA, and comparing with a regex

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Regular expressions and what finite machines cannot do

A regular expression is built from single symbols using three operations: union (a|b), concatenation (ab) and star (a*, zero or more repeats). The central theorem, Kleene's theorem, states that a language is described by a regular expression exactly when some DFA (or equivalently an NFA) accepts it. A construction due to Thompson turns any expression into an NFA, which is how many real regex engines begin, and the subset construction then yields a fast DFA. Practical regex libraries add extras such as back-references that go beyond regular languages, but the core is the same. For hands-on pattern work, see the Python regular expressions lesson.

Finite machines also have limits. A DFA has only finitely many states, so it cannot count without bound. Consider the language of strings 0^n 1^n (some zeros followed by the same number of ones). Read enough zeros and the machine must revisit a state, by the pigeonhole principle. Two different counts of zeros then lead to the same state, and from there the machine cannot tell them apart. So no DFA, and no regular expression, accepts this language. This argument is the idea behind the pumping lemma. Languages like balanced parentheses need a stronger machine with a stack, a pushdown automaton, which leads to context-free grammars and further to Turing machines.

Python Why a finite machine cannot count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main difference between a DFA and an NFA?

    A DFA has exactly one move per state and symbol. An NFA may branch, but it still recognizes only regular languages.
  2. 2. How many states can the subset construction produce from an NFA with n states, at most?

    Each DFA state is a subset of the NFA states, and an n-element set has 2^n subsets.
  3. 3. How do you turn a DFA for a language into a DFA for its complement?

    A DFA ends in exactly one state for each string, so flipping which states accept flips which strings are accepted.
  4. 4. Why can no DFA accept the language of strings 0^n 1^n?

    This is the pigeonhole argument behind the pumping lemma: finite memory cannot count without bound.

Summary

  • A DFA has finitely many states, one move per state and symbol, a start state and accepting states; simulating it is a table lookup in a loop.
  • An NFA may branch or use epsilon moves and accepts if any path accepts; simulate it by tracking the set of possible states.
  • The subset construction turns any NFA into an equivalent DFA, with at most 2^n states.
  • Regular languages are exactly those matched by DFAs, NFAs and regular expressions (Kleene's theorem), and are closed under union, intersection and complement.
  • Finite memory is a real limit: languages like 0^n 1^n need more powerful machines.

Next: Algorithms, Recursion and Growth, where we measure how much work an algorithm does.