Deterministic Finite Automata

A finite automaton is the simplest model of a computer: it reads its input one symbol at a time, from left to right, and its only memory is which of finitely many states it is in. When the input ends, it accepts if it is in an accepting state.

Definition

A deterministic finite automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q₀, F):

"Deterministic" means there is never a choice: from each state, each symbol leads to exactly one state. The extended transition function δ̂(q, w) follows a whole string: δ̂(q, ε) = q and δ̂(q, wa) = δ(δ̂(q, w), a). M accepts w when δ̂(q₀, w) ∈ F, and the language of M, L(M), is the set of all strings it accepts. The languages accepted by DFAs are exactly the regular languages.

Example: binary numbers divisible by 3

Read a binary number from the most significant bit. If the number so far has value v, reading bit b gives value 2v + b. So it is enough to remember v mod 3, which needs only three states:

(→ marks the start state and * the accepting state.) From remainder 1, reading 0 gives 2·1 + 0 = 2, reading 1 gives 2·1 + 1 = 3 ≡ 0; and so on.

Running a DFA is a loop of table lookups:

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

div3 = {"q0": {"0": "q0", "1": "q1"},
        "q1": {"0": "q2", "1": "q0"},
        "q2": {"0": "q1", "1": "q2"}}

for w in ["0", "11", "110", "1001", "111", "10010"]:
    print(f"{w:>6} = {int(w, 2):2}: {'accept' if run_dfa(div3, 'q0', {'q0'}, w) else 'reject'}")

     0 =  0: accept
    11 =  3: accept
   110 =  6: accept
  1001 =  9: accept
   111 =  7: reject
 10010 = 18: accept

Design patterns

Most DFA questions use one of a few ideas. The question to ask is always: what is the least I must remember about the input so far?

A dead state (trap state) is a non-accepting state that loops to itself on every symbol: once there, the string can never be accepted. A DFA must have a transition for every symbol, so dead states are needed whenever some prefix rules out acceptance. Diagrams often leave them out; GATE answers count them.

Here is the DFA for strings ending in 01. State A means "no progress", B "just read 0", C "just read 01":

The last row of the table is interesting: to know whether the 3rd symbol from the end is 1, the DFA must remember all of the last 3 symbols, because it never knows which symbol will be the last. In general, "the n-th symbol from the end is 1" needs 2ⁿ states, a striking contrast with the NFA in the next lesson, which needs only n + 1.

Product construction

If DFAs M₁ and M₂ accept L₁ and L₂, run them in parallel: a state of the product DFA is a pair (p, q), and δ((p, q), a) = (δ₁(p, a), δ₂(q, a)). Choosing the accepting pairs gives:

• L₁ ∩ L₂: accept (p, q) when p ∈ F₁ and q ∈ F₂,
• L₁ ∪ L₂: when p ∈ F₁ or q ∈ F₂,
• L₁ − L₂: when p ∈ F₁ and q ∉ F₂.

The product has |Q₁| × |Q₂| states. And the complement of L(M) needs no product at all: swap accepting and non-accepting states (the DFA must be complete, with its dead state included).

from itertools import product

def product_dfa(d1, d2, accept_pair):
    states = list(product(d1["delta"], d2["delta"]))
    delta = {(p, q): {a: (d1["delta"][p][a], d2["delta"][q][a]) for a in "01"} for p, q in states}
    accept = {(p, q) for p, q in states if accept_pair(p in d1["accept"], q in d2["accept"])}
    return delta, (d1["start"], d2["start"]), accept

even_zeros = {"delta": {"E": {"0": "O", "1": "E"}, "O": {"0": "E", "1": "O"}}, "start": "E", "accept": {"E"}}
ends_1 = {"delta": {"N": {"0": "N", "1": "Y"}, "Y": {"0": "N", "1": "Y"}}, "start": "N", "accept": {"Y"}}

delta, start, accept = product_dfa(even_zeros, ends_1, lambda a, b: a and b)
def run(w):
    s = start
    for c in w:
        s = delta[s][c]
    return s in accept
print(len(delta), "states; accepting:", sorted(accept))
print([w for w in ["1", "01", "001", "0101", "100", "0011"] if run(w)])

4 states; accepting: [('E', 'Y')]
['1', '001', '0101', '0011']

Practice questions

delta = {"q0": {"0": "q0", "1": "q1"}, "q1": {"0": "q2", "1": "q0"}, "q2": {"0": "q1", "1": "q2"}}
state = "q0"
for c in "1011":
    state = delta[state][c]
print(state)