Worked examples — Finite automata — DFA - formal definition (5-tuple), state diagrams

Before we start, one reminder in plain words so no symbol is unearned:

Recall The four symbols we reuse everywhere

$Q$ ::: the finite set of circles (states). $\Sigma$ ::: the alphabet — the letters the machine is allowed to read. $\delta (q,a)$ ::: "from circle $q$, reading letter $a$, hop to which circle?" — always exactly one answer. $\hat{\delta }(q,w)$ ::: run the whole string $w$ from $q$, one letter at a time, and report the final circle. Accept iff that circle is in $F$ (the double-circle set).

---

The scenario matrix

Every DFA question is really a combination of these "cells". The examples below are labelled by the cell(s) they cover, and together they hit every row.

Cell	What makes it different	Covered by
A. Normal accept	ordinary string that lands in $F$	Ex 1, Ex 4
B. Normal reject	ordinary string that lands outside $F$	Ex 1, Ex 3
C. Empty string $\epsilon$	"read nothing" — answer depends only on $q_0\in F?$	Ex 2
D. Degenerate / trap	missing arrows → hidden dead state; string that can never recover	Ex 3
E. Self-loop / irrelevant symbol	a letter that must NOT change memory	Ex 4
F. Length / counting memory	remember a count modulo $k$, not the count itself	Ex 4, Ex 5
G. Substring / suffix memory	remember "how much of a target pattern matched so far"	Ex 6
H. Real-world word problem	translate an English spec into a machine	Ex 7 (tokenizer)
I. Exam twist	given only the tuple, forecast the language, then verify	Ex 8

Geometric/diagram examples get a figure so you can watch the token hop.

---

Example 1 — Cells A & B: normal accept and normal reject

Forecast: State $t$ is a trap for good news — once you see a single 1 you can never leave $t$. So the machine accepts iff the string has at least one 1. $001$ has a 1 (expect accept); $000$ has none (expect reject).

Look at the figure — state $s$ means "no 1 yet", state $t$ means "seen a 1".

1. Trace $001$ from $s$. $s\stackrel{0}{\to }s\stackrel{0}{\to }s\stackrel{1}{\to }t$. Why this step? Each 0 is a self-loop (still no 1 seen); the final 1 flips us into the accept region $t$.
2. Check membership. End state $t\in F$ ⇒ accepted.
3. Trace $000$ from $s$. $s\stackrel{0}{\to }s\stackrel{0}{\to }s\stackrel{0}{\to }s$. Why this step? Only 0s means we never trigger the escape arrow to $t$.
4. Check membership. End state $s\notin F$ ⇒ rejected.

Verify: $001$ contains a 1 → should be in the language ✓. $000$ contains no 1 → correctly rejected ✓. This covers Cell A (accept) and Cell B (reject).

---

Example 2 — Cell C: the empty string $\epsilon$

Forecast: "Read nothing" cannot flip any state, so you stay put at the start. Since start $s$ is not accepting, expect reject.

1. Apply the base case of $\hat{\delta }$. By definition $\hat{\delta }(q,\epsilon )=q$, so $\hat{\delta }(s,\epsilon )=s$. Why this step? $\epsilon$ has no last letter, so the recursion never fires — reading nothing changes nothing.
2. Check membership. $s\notin F$ ⇒ rejected.

Verify: The rule "$\epsilon$ is accepted iff $q_0\in F$" says: here $q_0=s\notin F$, so reject. Matches ✓. (Sanity: $\epsilon$ contains zero 1s, so it should not be in "contains at least one 1" — correct.)

---

Example 3 — Cell D: the hidden dead / trap state

Forecast: A DFA's $\delta$ must be total — every (state, letter) pair needs a target. The missing arrows secretly all go to a dead state $d$ that loops on everything and never accepts. So any string that "goes off the drawn path" dies. $ba$ starts with the wrong letter (expect reject); $aba$ over-runs past ab (expect reject).

The figure shows the drawn arrows in orange and the implied dead-state arrows in dashed grey.

1. Complete the machine. Add $d$ with $\delta (d,a)=\delta (d,b)=d$, and route every missing pair to $d$: $\delta (p,b)=d,\delta (q,a)=d,\delta (r,a)=d,\delta (r,b)=d$. Why this step? Without this the object is not a DFA at all — you cannot leave a transition undefined.
2. Trace $ba$. $p\stackrel{b}{\to }d\stackrel{a}{\to }d$. Why this step? The first letter b is not the path's expected a, so we fall into the trap immediately, and traps are inescapable.
3. Check. $d\notin F$ ⇒ rejected.
4. Trace $aba$. $p\stackrel{a}{\to }q\stackrel{b}{\to }r\stackrel{a}{\to }d$. Why this step? We correctly matched ab and reached $r$, but the extra a has nowhere legal to go, so it dies.
5. Check. $d\notin F$ ⇒ rejected.

Verify: The language is exactly $\{ab\}$. $ba\ne ab$ ✓ rejected; $aba\ne ab$ ✓ rejected. Only the exact string $ab$ ($p\to q\to r$, ending in $F$) is accepted. Cell D covered.

---

Example 4 — Cells A, E, F: parity with an irrelevant symbol

Forecast: Count the as: abba has two as → even → expect accept. The bs should slide by harmlessly.

The figure: the a-arrows cross between the two circles (they flip parity), the b-arrows are loops (they do nothing).

1. Read a. $E\stackrel{a}{\to }O$. Why? First a makes the count odd.
2. Read b. $O\stackrel{b}{\to }O$. Why? A b is irrelevant to counting as → self-loop, parity unchanged.
3. Read b. $O\stackrel{b}{\to }O$. Why? Same — still one a seen.
4. Read a. $O\stackrel{a}{\to }E$. Why? Second a flips odd→even.
5. Check. End state $E\in F$ ⇒ accepted.

Verify: abba has exactly $2$ occurrences of a, and $2$ is even, so it should be accepted ✓. This shows Cell E (self-loop on the irrelevant b) and Cell F (memory = count mod 2).

---

Example 5 — Cell F pushed further: divisibility by 3

Forecast: $6=3\times 2$, divisible by 3 → expect accept. We only ever store the remainder (one of 3 values), never the whole number — that is why finite memory suffices.

Let's build the transitions from the rule $r_{\text{new}}=(2r+b)\mathrm{mod}3$:

$\delta (r_0,0)=r_0,\delta (r_0,1)=r_1,\delta (r_1,0)=r_2,\delta (r_1,1)=r_0,\delta (r_2,0)=r_1,\delta (r_2,1)=r_2.$

1. Read 1. $r_0$: $(2\cdot 0+1)\mathrm{mod}3=1\Rightarrow r_1$. Why? Value so far $=1$, remainder $1$.
2. Read 1. $r_1$: $(2\cdot 1+1)\mathrm{mod}3=3\mathrm{mod}3=0\Rightarrow r_0$. Why? Value so far $=3$, which is $\equiv 0$.
3. Read 0. $r_0$: $(2\cdot 0+0)\mathrm{mod}3=0\Rightarrow r_0$. Why? Value so far $=6$, still $\equiv 0$.
4. Check. End state $r_0\in F$ ⇒ accepted.

Verify: $110_2=6$, and $6\mathrm{mod}3=0$ ✓. Try a non-multiple mentally: $10_2=2$, $r_0\to r_1\to r_2$, ends $r_2\notin F$ → rejected, and $2$ is not divisible by 3 ✓. See Regular languages and the Pumping Lemma for why "divisible by $k$" is always regular.

---

Example 6 — Cell G: substring memory ("contains ab")

Forecast: Scan for an a immediately followed by a b. In baab the substring ab appears (positions 3–4). Expect accept. State $y$ is a good trap — once you've found ab, nothing can undo it.

The figure shows progress: how far along the pattern a→b we are.

1. Read b. $n_0\stackrel{b}{\to }{n}_0$. Why? No a seen yet; a leading b cannot begin ab.
2. Read a. $n_0\stackrel{a}{\to }{n}_1$. Why? We now hold a candidate a, waiting for a b.
3. Read a. $n_1\stackrel{a}{\to }{n}_1$. Why? Another a doesn't complete ab, but it's still a fresh candidate — stay in $n_1$.
4. Read b. $n_1\stackrel{b}{\to }y$. Why? a then b = pattern complete!
5. Check. End state $y\in F$ ⇒ accepted.

Verify: baab literally contains ab (chars 3–4) ✓. Compare with ba: $n_0\to n_0\to n_1$, ends $n_1\notin F$ → rejected, and ba has no ab ✓. This "how-much-matched" idea is exactly what Regular expressions compile down to.

---

Example 7 — Cell H: a real-world word problem (mini tokenizer)

Forecast: A number literal = at least one digit and no stray characters. So dd should accept, empty should reject (need at least one digit), and dx should reject (illegal character). This is the classic Cell H translation of English → machine.

Design. $Q=\{\text{start},\text{num},\text{err}\}$, start $=\text{start}$, $F=\{\text{num}\}$. $\delta (\text{start},d)=\text{num},\delta (\text{start},x)=\text{err},\delta (\text{num},d)=\text{num},\delta (\text{num},x)=\text{err},\delta (\text{err},d)=\delta (\text{err},x)=\text{err}.$ Why start ∉ F? Because $\epsilon$ (no digits at all) must be rejected — so the start state cannot be accepting. Why err is a trap? Once a bad character appears the whole token is invalid, forever.

1. Trace dd. $\text{start}\stackrel{d}{\to }\text{num}\stackrel{d}{\to }\text{num}$. Why? First digit reaches the accepting num; more digits self-loop there.
2. Check. $\text{num}\in F$ ⇒ accepted — "42" is a valid literal.
3. Trace $\epsilon$. $\hat{\delta }(\text{start},\epsilon )=\text{start}$. Why? Empty input — base case, stay at start.
4. Check. $\text{start}\notin F$ ⇒ rejected — an empty token is not a number ✓.
5. Trace dx. $\text{start}\stackrel{d}{\to }\text{num}\stackrel{x}{\to }\text{err}$. Why? Good first digit, then an illegal character drops us into the trap.
6. Check. $\text{err}\notin F$ ⇒ rejected — "4a" is not a valid integer literal ✓.

Verify: "42" accept ✓, "" reject ✓, "4a" reject ✓ — exactly what a real lexer's integer rule does. This same shape appears when building the scanner in Lexical analysis / tokenizers.

---

Example 8 — Cell I: the exam twist (given tuple → forecast language)

Forecast: 0 swaps $p\leftrightarrow q$; 1 never moves. Accepting state is $p$, and we start at $p$. So we accept iff the number of 0s is even. This is the Myhill–Nerode "what does each state remember?" reasoning in reverse.

1. Identify what each state means. $p=$ "even number of 0s so far", $q=$ "odd". Why? Only 0 toggles, and it toggles every time — that is exactly parity.
2. Trace $0011$. $p\stackrel{0}{\to }q\stackrel{0}{\to }p\stackrel{1}{\to }p\stackrel{1}{\to }p$. Why? Two 0s toggle twice (back to start); the 1s do nothing.
3. Check. End $p\in F$ ⇒ accepted. ($0011$ has two 0s → even ✓.)
4. Trace $010$. $p\stackrel{0}{\to }q\stackrel{1}{\to }q\stackrel{0}{\to }p$. Why? Two 0s (even) with a harmless 1 between them.
5. Check. End $p\in F$ ⇒ accepted. ($010$ has two 0s → even ✓.)

Verify: $L(M)=\{w:\#0(w)\text{ even}\}$. Both traces have an even count of 0s and both accept ✓. A quick reject-check: $0$ alone → $p\to q$, ends $q\notin F$, rejected, and one 0 is odd ✓. Note this is the same language as Example 4 read over a different alphabet — an NFA or subset construction could also produce it.

---

Recall Self-test: match each string to its cell and answer

$M_1$ on 000 — accept or reject, which cell? ::: Reject (Cell B); no 1 ever seen, stays in $s\notin F$. $\epsilon$ on any machine — what single fact decides it? ::: Whether $q_0\in F$ (Cell C). A string that "goes off the drawn arrows" ends where? ::: In the hidden dead/trap state, always rejected (Cell D). Divisible-by-3 machine on 110 — accept? ::: Accept; $110_2=6$, and $6\mathrm{mod}3=0$ (Cell F). Contains-ab machine on ba — accept? ::: Reject; reaches $n_1$ but never a following b, $n_1\notin F$ (Cell G).