Finite Automata

Maheshwari & Smid · Ch. 1 · Introduction to Theory of Computation

A deterministic finite automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F): finite states, an alphabet, a transition function, a start state, and accepting states. It reads a string one symbol at a time and either accepts or rejects. That is the simplest model of computation.

The five components

A DFA is defined by:

Q — a finite set of states
Σ — a finite alphabet of input symbols
δ — a transition function Q × Σ → Q
q₀ — the start state (q₀ ∈ Q)
F — a set of accepting states (F ⊆ Q)

Example: strings ending in "01"

Over the alphabet {0, 1}, this DFA accepts exactly the strings that end with "01".

Simulating a DFA

Scheme

; DFA for strings ending in "01"
; States: q0 (start), q1 (saw 0), q2 (accept: saw 01)

(define (dfa-step state symbol)
  (cond
    ((and (= state 0) (equal? symbol "0")) 1)
    ((and (= state 0) (equal? symbol "1")) 0)
    ((and (= state 1) (equal? symbol "0")) 1)
    ((and (= state 1) (equal? symbol "1")) 2)
    ((and (= state 2) (equal? symbol "0")) 1)
    ((and (= state 2) (equal? symbol "1")) 0)
    (else state)))

(define (run-dfa input)
  (define (step state i)
    (if (= i (string-length input))
        state
        (step (dfa-step state (substring input i (+ i 1)))
              (+ i 1))))
  (let ((final (step 0 0)))
    (= final 2)))

(display "101:  ") (display (run-dfa "101")) (newline)
(display "1001: ") (display (run-dfa "1001")) (newline)
(display "11:   ") (display (run-dfa "11")) (newline)
(display "01:   ") (display (run-dfa "01")) (newline)
(display "0101: ") (display (run-dfa "0101"))

Language recognition

The language of a DFA is the set of all strings it accepts. We write L(M) for the language recognized by machine M. A language is regular if some DFA recognizes it. Not all languages are regular: we will prove limits in Chapter 3.

Scheme

; A DFA that accepts strings with an even number of 1s.
; Two states: even (start, accept) and odd.

(define (even-ones input)
  (define (step state i)
    (if (= i (string-length input))
        state
        (let ((ch (substring input i (+ i 1))))
          (if (equal? ch "1")
              (step (- 1 state) (+ i 1))   ; toggle
              (step state (+ i 1))))))      ; stay
  (= (step 0 0) 0))  ; 0 = even (accepting)

(display "110:  ") (display (even-ones "110")) (newline)
(display "111:  ") (display (even-ones "111")) (newline)
(display "0000: ") (display (even-ones "0000")) (newline)
(display "1:    ") (display (even-ones "1")) (newline)
(display "empty: ") (display (even-ones ""))

Notation reference

Symbol	Meaning
Q	Finite set of states
Σ	Input alphabet
δ(q, a)	Transition function: state q reading symbol a
q₀	Start state
F	Set of accepting (final) states
L(M)	Language recognized by machine M

Neighbors

🔢 Discrete Math Ch.4 — graphs (automata are labeled directed graphs)
🔢 Discrete Math Ch.3 — propositional logic: automata can be expressed as logical formulas
🔗 Abstract Algebra Ch.1 — groups and monoids: FSAs are exactly the monoid recognizers
🪄 SICP Ch.11 — state machines in code: stream processors as explicit automata

by june.kim Nondeterminism →