Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 59 · Finite Automata

Introduction to Finite Automata and DFAs

Learn the formal definition of a DFA, how to read state diagrams and transition tables, dead states and acceptance, with a runnable Python DFA simulator.

A deterministic finite automaton (DFA) is the simplest machine in the theory of computation. It reads an input string one symbol at a time, left to right, and keeps track of nothing except which of a fixed number of states it is currently in. When the input ends, it answers yes (accept) or no (reject) depending on the state it stopped in. It is deterministic because in every state, each symbol leads to exactly one next state: there are never choices.

The formal definition

A DFA is a 5-tuple M = (Q, Σ, δ, q0, F):

  • Q: a finite set of states.
  • Σ: the input alphabet.
  • δ: Q × Σ → Q, the transition function. Given a state and a symbol, it returns exactly one state. It must be total: defined for every pair.
  • q0 in Q: the start state.
  • F ⊆ Q: the set of accepting (final) states.

The machine accepts a string w if, starting at q0 and following δ for each symbol of w, it finishes in a state of F. The set of all accepted strings is the language of M, L(M). A language is called regular if some DFA recognizes it.

Reading a state diagram

A state diagram draws states as circles, transitions as labeled arrows, the start state with an incoming arrow, and accepting states with a double circle. Here is a DFA over {0, 1} that accepts exactly the strings ending in 01:

flowchart LR
    start(( )) --> q0
    q0(("q0")) -->|"0"| q1(("q1"))
    q0 -->|"1"| q0
    q1 -->|"0"| q1
    q1 -->|"1"| q2((("q2")))
    q2 -->|"0"| q1
    q2 -->|"1"| q0

q2 is the accepting state (double circle). Each state has exactly one outgoing arrow for each of 0 and 1.

Each state has a meaning, which is how you design and check DFAs:

  • q0: the input so far does not end in 0 (empty, or ends in 1 without a preceding 0).
  • q1: the last symbol read was 0, so a 1 next would complete 01.
  • q2: the input ends in 01.

The same machine as a transition table, with the accepting state marked * and the start state marked ->:

State on 0 on 1
-> q0 q1 q0
q1 q1 q2
* q2 q1 q0

Running a DFA in code

Because δ is just a lookup table, a DFA simulator is only a few lines. We will reuse this exact pattern throughout the chapter.

Python A DFA simulator

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.

The trace shows what "memory of a DFA" means: after each symbol, only the new state is kept. The whole input history has been compressed into one of three labels.

The extended transition function

Mathematicians extend δ to whole strings. Write δ*(q, w) for the state reached from q after reading w. It is defined recursively: δ*(q, ε) = q, and δ*(q, wa) = δ(δ*(q, w), a). Then M accepts w exactly when δ*(q0, w) is in F. This recursive form is what you use in proofs, and the loop in run above computes it.

Dead (trap) states

A DFA must define a move for every state and symbol, so machines that "should fail" on some input route it to a dead state (or trap state): a non-accepting state from which every transition loops back to itself. Consider the language of strings that start with a over {a, b}:

flowchart LR
    start(( )) --> s
    s(("s")) -->|"a"| ok((("ok")))
    s -->|"b"| dead(("dead"))
    ok -->|"a, b"| ok
    dead -->|"a, b"| dead

If the first symbol is b the machine falls into dead and can never accept. Drawings often omit the dead state, but it is still part of the DFA.

Python Dead states and counting visits

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.

For each length n ≥ 1, exactly half the strings (2^(n-1)) start with a. Notice that the empty string is rejected: the start state s is not accepting.

Designing DFAs: a checklist

  1. Decide what the machine must remember about the prefix read so far. That is the meaning of each state.
  2. Create a state for each distinct thing to remember, and mark the ones where the string would be accepted if it ended now.
  3. For each state and each symbol, decide the next state. Do not forget any pair.
  4. Add a dead state if some input prefixes can never be fixed.
  5. Test on short strings including ε.

The next lesson applies the checklist to the classic design problems, and later lessons show how to shrink and combine DFAs. Different problems need different amounts of memory: "even number of a's" needs two states, "ends in 01" needs three, and a^n b^n needs infinitely many, which is why it is not regular.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What must the transition function δ of a DFA satisfy?

    A DFA is deterministic and total: every state has exactly one next state for every input symbol.
  2. 2. When does a DFA accept a string w?

    Acceptance depends only on the final state after the last symbol. Passing through an accepting state in the middle does not matter.
  3. 3. In the 'ends in 01' DFA, after reading 1100 which state is the machine in?

    q0 -1-> q0 -1-> q0 -0-> q1 -0-> q1. The last symbol was 0, so the machine is in q1.
  4. 4. What is a dead (trap) state?

    Once in a dead state the machine can never accept, so it absorbs all inputs that have already gone wrong.
  5. 5. A language is regular if...

    The class of regular languages is defined as those recognized by DFAs (equivalently by NFAs or regular expressions).

Summary

  • A DFA is (Q, Σ, δ, q0, F) with a total transition function; each input produces exactly one path.
  • It accepts w when δ*(q0, w) is an accepting state; the set of accepted strings is a regular language.
  • State diagrams and transition tables are two views of the same δ.
  • Dead states handle prefixes that can never be completed into a valid string.
  • Design by deciding what each state remembers.

Next: Designing DFAs: Common Patterns