Chapter 04 of 34

Deterministic Finite Automata (DFA)

In Finite Automata we met machines that read a string symbol by symbol and remember only their current state. We described them informally with diagrams. To prove things about these machines, and to answer GATE questions without ambiguity, we need a definition with no loose ends.

The Deterministic Finite Automaton (DFA) is the version where every move is completely determined: in each state, for each input symbol, there is exactly one next state. No guessing, no choices, no getting stuck. This makes DFAs easy to simulate, easy to implement in hardware and software, and the reference point against which all other finite automata are measured.

In this chapter we give the formal 5-tuple definition, define the extended transition function that tells us where a whole string takes the machine, trace several DFAs step by step, deal with dead states and complete versus partial DFAs, and show how to complement a DFA. Every DFA here was simulated and checked against its language definition on all strings up to length 10.


Formal Definition

A Deterministic Finite Automaton is a 5-tuple M = (Q, Σ, δ, q0, F) where:
Q is a finite, non-empty set of states;
Σ is a finite input alphabet;
δ : Q × Σ → Q is the transition function;
q0 ∈ Q is the start state;
F ⊆ Q is the set of final (accepting) states.

The word that makes it "deterministic" is hidden in the type of δ: δ : Q × Σ → Q is a function. For every pair (state, symbol) it returns exactly one state. Not zero (the machine never gets stuck), not two (the machine never has to choose).

So a DFA with |Q| = n states over an alphabet with |Σ| = m symbols has exactly n × m transitions, one for each cell of its transition table.


A First Complete Example

Language: L = {w ∈ {0,1}* : w ends with 01}.

What must the machine remember? Only how much of the pattern "01" it has just seen at the end of the input:

  • q0: the input so far does not end in 0 or 01 (this includes ε, and any string ending in 11 or a lone 1).

  • q1: the input so far ends in 0 (we may be starting a "01").

  • q2: the input so far ends in 01 (accept if the input stops here).

Transitions, with the reason for each:

  • q0 on 0 → q1 (now ends in 0). q0 on 1 → q0 (ends in 1, but not 01).

  • q1 on 0 → q1 (still ends in 0). q1 on 1 → q2 (now ends in 01).

  • q2 on 0 → q1 (ends in 0 again). q2 on 1 → q0 (ends in 11, the pattern is broken).

Formally: M = ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) with δ given by the table:

δ

0

1

→ q0

q1

q0

q1

q1

q2

* q2

q1

q0

          1                0
        +---+            +---+
        |   v            |   v
  -->  ( q0 ) ---0---> ( q1 ) ---1---> (( q2 ))
        ^  ^               ^                | |
        |  |               +------0---------+ |
        |  +-----------------1----------------+
   (q2 on 0 goes back to q1;  q2 on 1 goes back to q0)

Count the arrows: 3 states × 2 symbols = 6 transitions, one leaving every state on every symbol. That is the hallmark of a complete DFA.


The Extended Transition Function δ̂

δ tells us what one symbol does. We want to know what a whole string does. The extended transition function δ̂ (read "delta hat"; some books write δ*) : Q × Σ* → Q is defined by induction on the length of the string:

Basis: δ̂(q, ε) = q.
Step: δ̂(q, wa) = δ(δ̂(q, w), a), for any string w and symbol a.

In words: reading nothing leaves you where you are; to read wa, first read w, then take one ordinary step on a. It is exactly "apply δ symbol after symbol", written precisely.

Worked Example: δ̂(q0, 1101)

δ̂(q0, ε)    = q0
δ̂(q0, 1)    = δ(δ̂(q0, ε), 1)   = δ(q0, 1) = q0
δ̂(q0, 11)   = δ(δ̂(q0, 1), 1)   = δ(q0, 1) = q0
δ̂(q0, 110)  = δ(δ̂(q0, 11), 0)  = δ(q0, 0) = q1
δ̂(q0, 1101) = δ(δ̂(q0, 110), 1) = δ(q1, 1) = q2     q2 ∈ F  =>  1101 is ACCEPTED

Many books also write the run as a sequence of configurations (instantaneous descriptions). A configuration is a pair (current state, unread input), and ⊢ means "moves in one step to":

(q0, 1101) ⊢ (q0, 101) ⊢ (q0, 01) ⊢ (q1, 1) ⊢ (q2, ε)      final state, accept

(q0, 0110) ⊢ (q1, 110) ⊢ (q2, 10) ⊢ (q0, 0) ⊢ (q1, ε)      q1 not final, reject

Notice in the second run that the machine passed through the final state q2 after "01", but kept going. Only the state after the last symbol counts.


The Language of a DFA

A DFA M accepts w if δ̂(q0, w) ∈ F. The language of M is L(M) = {w ∈ Σ* : δ̂(q0, w) ∈ F}.

Because δ is a function, every input string has exactly one run, and that run always reads the whole string. So for a DFA, "accept" and "reject" are always well defined, and the machine always halts after |w| steps. This is why DFA membership testing takes O(|w|) time and O(1) extra memory.

For our example, L(M) = {w : w ends with 01}. To be sure, we must check two directions: every string ending in 01 is accepted (it reaches q2, because the last two symbols always take any state through q1 to q2: δ(anything, 0) = q1 and δ(q1, 1) = q2), and every accepted string ends in 01 (the only way into q2 is the transition q1 →1→ q2, and the only ways into q1 read a 0).

Simulating a DFA in Code

A DFA is just a lookup table in a loop:

# DFA for binary strings ending in 01
delta = {
    ('q0', '0'): 'q1', ('q0', '1'): 'q0',
    ('q1', '0'): 'q1', ('q1', '1'): 'q2',
    ('q2', '0'): 'q1', ('q2', '1'): 'q0',
}
start, finals = 'q0', {'q2'}

def run(w):
    q = start
    path = [q]
    for symbol in w:
        q = delta[(q, symbol)]      # exactly one next state: deterministic
        path.append(q)
    return q in finals, path

for w in ['1101', '0110', '01001', '', '01']:
    ok, path = run(w)
    print(f"{w or 'ε':6} {' -> '.join(path):32} {'ACCEPT' if ok else 'REJECT'}")

Output:

1101   q0 -> q0 -> q0 -> q1 -> q2       ACCEPT
0110   q0 -> q1 -> q2 -> q0 -> q1       REJECT
01001  q0 -> q1 -> q2 -> q1 -> q1 -> q2 ACCEPT
ε      q0                               REJECT
01     q0 -> q1 -> q2                   ACCEPT

Example 2: Even Number of 0s

L = {w ∈ {0,1}* : |w|0 is even}. Two states, tracking the parity of 0s: E (even, start and final) and O (odd).

δ

0

1

→ * E

O

E

O

E

O

Run on 1001: E →1→ E →0→ O →0→ E →1→ E. Accept (two 0s). Run on 010: E →0→ O →1→ O →0→ E. Accept (two 0s). Run on 0: E → O, reject. And ε is accepted, because the start state E is final (zero 0s is even).


Complete DFAs, Partial DFAs and Dead States

Language: strings over {a, b} that start with a.

After reading a first symbol a, the answer is "yes" whatever follows. After a first symbol b, the answer is "no" whatever follows. We need a state for the second case too, because δ must be defined everywhere:

δ

a

b

→ q0

q1

qd

* q1

q1

q1

qd

qd

qd

  -->  ( q0 ) ---a---> (( q1 )) ---+
          |               ^         | a, b
          b               +---------+
          |
          v
        ( qd ) ---+
          ^       | a, b          qd = dead (trap) state
          +-------+

A dead state (trap state) is a non-final state that goes to itself on every symbol. Once the machine enters it, no continuation can lead to acceptance.

Many textbooks and diagrams leave the dead state out to reduce clutter: any missing transition is understood to go to an invisible dead state. Such a drawing is called a partial DFA (δ is a partial function). That is fine for reading a diagram, but remember two things:

  • The strict definition requires δ to be total, so the "official" DFA has the dead state.

  • When GATE asks for "the number of states in the minimal DFA", the expected answer includes the dead state if one is needed. For "starts with a", the answer is 3, not 2.


Complementing a DFA

The complement of L is Σ* - L. For a complete DFA this is wonderfully easy:

Keep everything the same and swap final and non-final states: F becomes Q - F. The new DFA accepts exactly Σ* - L(M).

Why it works: each string has exactly one run, ending in exactly one state. That state was final before if and only if it is non-final now.

Applied to "ends with 01": make q0 and q1 final and q2 non-final. The new DFA accepts every string that does not end with 01, including ε, 0, 1 and 0110.

The Partial-DFA Trap

The swap trick fails if the dead state was left out. Take "starts with a" without qd: q0 →a→ q1, q1 loops on a and b, and q0 has no move on b. Swapping gives F = {q0}. That machine accepts only ε (on input b it gets stuck and rejects). But the true complement is {ε} ∪ {strings starting with b}, which includes b, ba, bb, .... The strings that "fell off" the partial DFA were never in any state, so swapping could not turn them into accepted strings.

Rule: always complete the DFA (add the dead state) before complementing. With qd present, swapping gives F = {q0, qd}, which is correct.


Some Useful Facts About DFAs

Fact

Why it is true

Every input has exactly one run, and the DFA always halts after |w| steps.

δ is a total function.

ε ∈ L(M) if and only if q0 ∈ F.

δ̂(q0, ε) = q0.

L(M) = ∅ if and only if no final state is reachable from q0.

A reachable final state gives an accepted string (the path's labels). This makes emptiness a simple graph search.

L(M) = Σ* if and only if every reachable state is final.

Apply the previous fact to the complement DFA.

Unreachable states can be deleted without changing L(M).

No run ever visits them.

Many different DFAs accept the same language, but there is a unique smallest one (up to renaming states).

Proved and computed in DFA Minimization.

With n states, m symbols and a fixed start state, there are nnm · 2n different DFAs.

Each of the nm table cells has n choices; each state is final or not.


Solved GATE-Style Problem: Counting DFAs

Question. Consider DFAs over Σ = {a, b} with exactly two states X and Y, where X is the start state. How many such DFAs accept the empty language?

Solution. Total DFAs: 22×2 transition tables × 22 choices of F = 16 × 4 = 64. The language is empty exactly when no final state is reachable from X.

  • F = ∅: nothing is ever accepted, whatever the transitions. 16 DFAs.

  • F = {Y}: the language is empty only if Y is unreachable, i.e. both of X's transitions go to X (1 way), while Y's two transitions are arbitrary (2 × 2 = 4 ways). 4 DFAs.

  • F = {X} or {X, Y}: X is the start state and is final, so ε is accepted. 0 DFAs.

Answer: 16 + 4 = 20. (We confirmed this by enumerating all 64 DFAs in a script.)


Common Mistakes

  • Missing transitions in a "DFA". In a complete DFA every state has exactly one outgoing transition per symbol. Count them: n states × m symbols.

  • Two transitions on the same symbol from one state. That makes it an NFA, not a DFA.

  • Accepting because a final state was visited mid-way. Only the state after the last symbol decides.

  • Forgetting ε. Check whether the start state should be final.

  • Complementing a partial DFA by swapping. Add the dead state first.

  • Not counting the dead state in "minimum number of states" answers.

  • Writing δ̂(q, wa) = δ(q, wa). δ only takes single symbols; δ̂ takes strings.


Interview and Exam Questions

Define a DFA formally.

A 5-tuple (Q, Σ, δ, q0, F): finite state set Q, input alphabet Σ, total transition function δ : Q × Σ → Q, start state q0 ∈ Q and final states F ⊆ Q. It accepts w if δ̂(q0, w) ∈ F.

What makes a finite automaton deterministic?

For every state and every input symbol there is exactly one next state, so each input has exactly one run.

Define the extended transition function.

δ̂(q, ε) = q and δ̂(q, wa) = δ(δ̂(q, w), a). It gives the state reached from q after reading a whole string.

A DFA has 5 states over a 3-symbol alphabet. How many transitions does it have?

5 × 3 = 15, one for each (state, symbol) pair.

How do you build a DFA for the complement of L(M)?

Make sure M is complete (add a dead state if needed), then swap final and non-final states.

How can you check whether a DFA accepts any string at all?

Run BFS or DFS from the start state; the language is non-empty if and only if some final state is reachable.

What is the time complexity of checking whether a DFA accepts a string of length n?

O(n): one table lookup per symbol, with constant extra memory.

How many DFAs with 3 states over {0, 1} with a fixed start state exist?

33×2 × 23 = 729 × 8 = 5832.


Summary

  • A DFA is a 5-tuple (Q, Σ, δ, q0, F) with a total transition function δ : Q × Σ → Q.

  • The extended transition function δ̂ runs the DFA on whole strings: δ̂(q, ε) = q, δ̂(q, wa) = δ(δ̂(q, w), a).

  • M accepts w if δ̂(q0, w) ∈ F; L(M) is the set of such strings. Each input has exactly one run, checked in O(|w|) time.

  • A dead state is a non-final trap; partial DFAs hide it, but the formal DFA (and minimal state counts) include it.

  • Complement a complete DFA by swapping final and non-final states.

  • Emptiness and universality of a DFA are simple reachability checks.

  • Next, Designing DFAs: Solved Problems turns all this into a toolkit for building DFAs for typical exam languages.