How unit 2 is examined
This unit covers NFA, DFA design, subset construction, minimization, regular expressions, Arden's theorem, closure properties and 2-way DFA; DFA design, regular expressions and Arden's theorem carry the most marks.
Non Deterministic Finite Automata (NDFA)
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>An NFA is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ whose transition function $\delta: Q\times\Sigma \to 2^{Q}$ gives a set of possible next states, and a string is accepted if at least one path ends in a final state.</mark>
Key points.
- An NFA may have zero, one or many moves on the same symbol, whereas a DFA has exactly one.
- An NFA may also have $\epsilon$ (lambda) moves that change state without reading input.
- Acceptance needs only one successful path; the other paths are ignored.
- Every NFA has an equivalent DFA (subset construction), so NFAs and DFAs accept exactly the regular languages.
- An NFA is easier to design and smaller, but a DFA is easier to simulate; converting can cost up to $2^n$ states.
| Basis | DFA | NFA |
|---|---|---|
| $\delta$ | $Q\times\Sigma\to Q$ | $Q\times\Sigma\to 2^Q$ |
| Next state | exactly one | zero, one or many |
| $\epsilon$-move | not allowed | allowed |
| Dead state | needed for a total function | can be omitted |
| Acceptance | the single path ends in F | some path ends in F |
Example. NFA for strings over $\{0,1,2\}$ whose decimal value is divisible by 3. States are remainders; on digit $d$ the new remainder is $(10r+d) \bmod 3=(r+d)\bmod 3$. Start and final state is $q_0$.
| State | 0 | 1 | 2 |
|---|---|---|---|
| $\rightarrow *q_0$ | $q_0$ | $q_1$ | $q_2$ |
| $q_1$ | $q_1$ | $q_2$ | $q_0$ |
| $q_2$ | $q_2$ | $q_0$ | $q_1$ |
Answer frame. Open with the 5-tuple and the meaning of $\delta$; draw one small DFA and one NFA (for example NFA for strings ending in 01); develop the comparison table; close with "both accept exactly the regular languages".
Asked: [7 marks] (Nov 2022) Design a NFA that accepts the language over $\Sigma=\{0,1,2\}$ where the decimal equivalent is divisible by 3. Asked: [7 marks] (Dec 2025) Explain deterministic and non-deterministic finite automata with examples.
Deterministic finite automata machines
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. ==A DFA is a 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$: $Q$ finite states, $\Sigma$ input alphabet, $\delta:Q\times\Sigma\to Q$ total transition function, $q_0\in Q$ start state, $F\subseteq Q$ final states; $L(M)=\{w \mid \delta^*(q_0,w)\in F\}$.==
Key points.
- $\delta$ is total and deterministic: every state has exactly one move on every symbol, so a computation is unique.
- A trap (dead) state is a non-final state whose every transition returns to itself; once entered, the string can never be accepted.
- To design a DFA, decide what each state remembers (count, last symbols, remainder) and add a transition for every symbol.
- Household applications: vending machine (coins seen), lift controller (floor and direction), traffic light (fixed cycle of states), digital lock (code sequence).
Diagram. At most 3 a's over $\{a,b\}$. States $q_0..q_3$ count a's, $D$ is the dead state; $b$ loops on $q_0..q_3$, and $a,b$ loop on $D$. Final: $q_0,q_1,q_2,q_3$.
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 596 80" width="596" height="80" role="img" aria-label="At most 3 a's: b loops on q0-q3, a and b loop on trap D; q0-q3 final"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah4)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah4)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah4)"/><path class="e" d="M446,40 L535,40" marker-end="url(#ah4)"/><g class="wl"><rect x="94.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="40" dy=".35em" text-anchor="middle">a</text></g><g class="wl"><rect x="223.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="40" dy=".35em" text-anchor="middle">a</text></g><g class="wl"><rect x="352.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="40" dy=".35em" text-anchor="middle">a</text></g><g class="wl"><rect x="481.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="491.5" y="40" dy=".35em" text-anchor="middle">a</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">q0</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">q1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">q2</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">q3</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">At most 3 a's: b loops on q0-q3, a and b loop on trap D; q0-q3 final</figcaption></figure>
Design (binary multiple of 3). State = remainder, $\delta(r,b)=(2r+b)\bmod 3$; start and final $q_0$. Checked: 11 (=3) and 110 (=6) accepted.
| State | 0 | 1 |
|---|---|---|
| $\rightarrow *q_0$ | $q_0$ | $q_1$ |
| $q_1$ | $q_2$ | $q_0$ |
| $q_2$ | $q_1$ | $q_2$ |
Not ending in 01. $q_0$ (start, last symbol not 0), $q_1$ (last symbol 0), $q_2$ (ends in 01, non-final). Final: $q_0,q_1$.
| State | 0 | 1 |
|---|---|---|
| $\rightarrow *q_0$ | $q_1$ | $q_0$ |
| $*q_1$ | $q_1$ | $q_2$ |
| $q_2$ | $q_1$ | $q_0$ |
Start and end with different symbols. States remember first symbol and last symbol; final $B,D$.
| State | 0 | 1 |
|---|---|---|
| $\rightarrow s$ | $A$ (began 0, ends 0) | $C$ (began 1, ends 1) |
| $A$ | $A$ | $*B$ (began 0, ends 1) |
| $*B$ | $A$ | $B$ |
| $C$ | $*D$ (began 1, ends 0) | $C$ |
| $*D$ | $D$ | $C$ |
1001 without overlap. $s_i$ = matched prefix length $i$; $s_4$ is final and, for no overlap, restarts as $s_0$ (the last 1 is not reused).
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 596 80" width="596" height="80" role="img" aria-label="1001 detector: s0 loops on 0, s1 loops on 1; s4 accepts then behaves as s0"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah5)"/><path class="e" d="M186,48.4 Q233.5,72 279.2,49.3" marker-end="url(#ah5)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah5)"/><path class="e" d="M446,40 L535,40" marker-end="url(#ah5)"/><path class="e" d="M408,40 L61,40" marker-end="url(#ah5)"/><path class="e" d="M281,31.6 Q233.5,8 187.8,30.7" marker-end="url(#ah5)"/><path class="e" d="M537,40 L61,40" marker-end="url(#ah5)"/><path class="e" d="M537,40 L190,40" marker-end="url(#ah5)"/><g class="wl"><rect x="94.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="40" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="223.5" y="51.4" width="19.2" height="18" rx="9"/><text class="t" x="233.1" y="60.4" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="352.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="40" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="481.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="491.5" y="40" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="223.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="40" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="224.3" y="10.6" width="19.2" height="18" rx="9"/><text class="t" x="233.9" y="19.6" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="288.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="352.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="40" dy=".35em" text-anchor="middle">1</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">s0</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">s1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">s2</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">s3</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">s4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">1001 detector: s0 loops on 0, s1 loops on 1; s4 accepts then behaves as s0</figcaption></figure>
Q2 machines over $\{a,b\}$ (all with dead state $d$ where needed):
- (i) exactly one a: $p_0\xrightarrow{a}p_1$, $b$ loops; $p_1\xrightarrow{a}d$, $b$ loops on $p_1$; final $p_1$.
- (ii) at least one a: same but $p_1$ loops on $a,b$; final $p_1$.
- (iii) $a^+bb$: $r_0\xrightarrow{a}r_1$, $r_0\xrightarrow{b}d$; $r_1$ loops on $a$, $r_1\xrightarrow{b}r_2\xrightarrow{b}r_3$ (final); $r_2\xrightarrow{a}d$; $r_3\to d$ on $a,b$.
Answer frame. Open with the 5-tuple; draw the labelled transition diagram with start arrow and double-circled finals; give the transition table; develop what each state remembers; test on two strings (one accepted, one rejected); close with the accepting condition.
Pitfall: Forgetting the dead state (an incomplete $\delta$) makes it an NFA, not a DFA. Asked: [14 marks] (Nov 2019) Describe NFA and DFA in brief; explain construction of DFA for $r=(0+1)^*(00+11)(0+1)^*$. Asked: [14 marks] (May 2023) For $\Sigma=\{a,b\}$ construct DFAs for (i) exactly one a, (ii) at least one a, (iii) at least one a followed by exactly two b's. Asked: [7 marks] (Dec 2020) Design DFA that accepts all strings with at most 3 a's. Asked: [7 marks] (Jun 2020) What is a trap state in FA? Explain the properties of the transition function. Asked: [7 marks] (Jun 2020) Define DFA; list three household applications of finite automata. Asked: [7 marks] (Nov 2022) Design DFA for detecting 1001 sequence without overlap over $\{0,1\}$. Asked: [7 marks] (Nov 2023) Draw a DFA to accept strings of 0's and 1's not ending with 01. Asked: [7 marks] (Nov 2023) Design a DFA accepting binary strings that are multiples of 3. Asked: [8 marks] (Dec 2024) What is a DFA? Design a DFA over $\{0,1\}$ accepting all strings starting and ending with different symbols.
Conversion of NDFA to DFA
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. ==Subset construction builds an equivalent DFA whose states are sets of NFA states: $\delta_D(S,a)=\bigcup_{q\in S}\delta_N(q,a)$, the start state is $\epsilon\text{-closure}(q_0)$, and any subset containing an NFA final state is final.==
Steps.
Step 1: Start state of DFA = epsilon-closure of q0 (just {q0} if no epsilon moves).
Step 2: For each new subset S and each symbol a, compute the union of moves, then its epsilon-closure.
Step 3: Add every new subset to the table; repeat until no new subset appears.
Step 4: Mark as final every subset containing an NFA final state; draw the DFA.
Key points. Only reachable subsets are built; the empty subset is the dead state; worst case an $n$-state NFA needs $2^n$ DFA states.
Example. $\delta(q_0,a)=\{q_0,q_1\}$, $\delta(q_0,b)=\{q_0\}$, $\delta(q_1,b)=\{q_1\}$, final $q_1$.
| DFA state | a | b |
|---|---|---|
| $\rightarrow\{q_0\}$ | $\{q_0,q_1\}$ | $\{q_0\}$ |
| $*\{q_0,q_1\}$ | $\{q_0,q_1\}$ | $\{q_0,q_1\}$ |
Answer: 2 DFA states, $\{q_0,q_1\}$ final (a is never seen: stay in $\{q_0\}$; after the first a everything is accepted).
Figure-NFA (states 1-6, final 6, $1\xrightarrow{\lambda}4$). Start $=\{1,4\}$; a gives $\{2\}$, b gives $\{5\}$; $\{2\}\xrightarrow{b}\{3\}$; $\{5\}\xrightarrow{b}\{6\}$ (final); $\{3\}\xrightarrow{a}\{1,3,4\}$; continue until no new subset.
Answer frame. Open with "each DFA state is a subset of NFA states"; write the NFA table; build the DFA table row by row; draw the DFA; close with the finals.
Asked: [7 marks] (Nov 2022, Dec 2025) Convert the given NFA to an equivalent DFA (states $\{q_0,q_1\}$, $\delta(q_0,a)=\{q_0,q_1\}$, $\delta(q_0,b)=\{q_0\}$, $\delta(q_1,b)=\{q_1\}$, final $q_1$; and the 6-state NFA with a $\lambda$-move).
Minimization of automata machines
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>Minimization merges equivalent states: two states $p,q$ are equivalent if for every string $w$, $\delta^*(p,w)$ and $\delta^*(q,w)$ are both final or both non-final; Myhill-Nerode gives the minimum DFA, one state per equivalence class.</mark>
Steps.
Step 1: Remove unreachable states.
Step 2: Partition into final and non-final states (0-equivalence).
Step 3: Split a block if two of its states go to different blocks on some symbol (k+1 equivalence).
Step 4: Repeat until no block splits; each block becomes one state.
Step 5: Rebuild the transition table and diagram.
Example (Jun 2025). Final $\{C\}$, non-final $\{A,B,D\}$. On a: A to B, B to C, D to C, so A splits off. B and D both go to C on a and to A on b, so they stay together.
| Block | a | b |
|---|---|---|
| $\rightarrow A$ | $\{B,D\}$ | $A$ |
| $\{B,D\}$ | $C$ | $A$ |
| $*C$ | $C$ | $\{B,D\}$ |
Answer: 3 states: $A$, $\{B,D\}$, $C$.
Example (Dec 2024). Finals $\{Q_1,Q_2,Q_5\}$, non-finals $\{Q_0,Q_3,Q_4\}$. $Q_5$ loops on itself but $Q_1,Q_2$ go to non-finals, so $Q_5$ splits; $Q_0$ goes to finals, $Q_3,Q_4$ go to $Q_5$, so $Q_0$ splits. $Q_1\equiv Q_2$ and $Q_3\equiv Q_4$.
Answer: Chain of 4 states $Q_0\to\{Q_1,Q_2\}\to\{Q_3,Q_4\}\to Q_5$ on both symbols, $Q_5$ loops on 0,1 (final states $\{Q_1,Q_2\}$ and $Q_5$).
Answer frame. Open with the equivalence definition; write the partition steps as $\Pi_0,\Pi_1,\ldots$; draw the reduced table and diagram; close with the number of states removed.
Asked: [8 marks] (Dec 2024) Minimize the DFA using the Myhill-Nerode theorem. Asked: [7 marks] (Jun 2025) Minimize the DFA with states $\{A,B,C,D\}$, initial $A$, final $C$, transitions $A\to aB,bA;\ B\to aC,bA;\ C\to aC,bD;\ D\to aC,bA$.
Regular expression
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. <mark>A regular expression describes a regular language recursively: $\emptyset$, $\epsilon$ and each $a\in\Sigma$ are regular expressions, and if $r,s$ are regular expressions so are $r+s$ (union), $rs$ (concatenation) and $r^*$ (Kleene closure).</mark>
Key points.
- Precedence is closure, then concatenation, then union.
- $L(r+s)=L(r)\cup L(s)$, $L(rs)=L(r)L(s)$, $L(r^*)=\bigcup_{i\ge0}L(r)^i$.
- Useful identities: $\epsilon r=r$, $\emptyset r=\emptyset$, $r+r=r$, $(r^*)^*=r^*$, $(r+s)^*=(r^*s^*)^*$.
- Regular expressions and finite automata are equivalent: RE to NFA by Thompson construction, DFA to RE by Arden's theorem or state elimination.
- A DFA is converted to an RE by writing one equation per state and solving with Arden's theorem.
Standard expressions.
| Language | Regular expression |
|---|---|
| exactly two a's over $\{a,b\}$ | $b^*ab^*ab^*$ |
| $a^x$, $x$ divisible by 3 or 5 | $(aaa)^*+(aaaaa)^*$ |
| contains 1100 | $(0+1)^*1100(0+1)^*$ |
| ends with 00 | $(0+1)^*00$ |
| $\{\Lambda,a,aa,aaa,\ldots\}$ | $a^*$ |
| ends with ab | $(a+b)^*ab$ |
FA for $(0+1)^*(00+11)(0+1)^*$ (strings containing 00 or 11). $S$ start, $A$ last symbol 0, $B$ last symbol 1, $F$ final (once a double is seen, stay).
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="Contains 00 or 11: F is final and loops on 0,1; S start, A last 0, B last 1"><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,117.5 L193.2,49.4" marker-end="url(#ah6)"/><path class="e" d="M57,134.5 L193.2,202.6" marker-end="url(#ah6)"/><path class="e" d="M205.4,57.8 Q180,126 204.7,192.3" marker-end="url(#ah6)"/><path class="e" d="M218.6,194.2 Q244,126 219.3,59.7" marker-end="url(#ah6)"/><path class="e" d="M229,48.5 L365.2,116.6" marker-end="url(#ah6)"/><path class="e" d="M229,203.5 L365.2,135.4" marker-end="url(#ah6)"/><g class="wl"><rect x="116.4" y="74" width="19.2" height="18" rx="9"/><text class="t" x="126" y="83" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="116.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="126" y="169" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="182.9" y="116.5" width="19.2" height="18" rx="9"/><text class="t" x="192.5" y="125.5" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="221.9" y="117.5" width="19.2" height="18" rx="9"/><text class="t" x="231.5" y="126.5" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="288.4" y="74" width="19.2" height="18" rx="9"/><text class="t" x="298" y="83" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="288.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">1</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Contains 00 or 11: F is final and loops on 0,1; S start, A last 0, B last 1</figcaption></figure>
Counting states for $(a+b)ab(a+b)$ (Jun 2025). The language is exactly the strings $xaby$ of length 4, with $x,y\in\{a,b\}$ (a wildcard, then a, then b, then a wildcard). A minimal NFA is a chain of 5 states $q_0\to q_1\to q_2\to q_3\to q_4$ (final $q_4$; $q_0,q_4$ on a,b; $q_1$ on a; $q_2$ on b; $q_3$ on a,b). The DFA is the same chain plus a dead state, since a wrong symbol needs somewhere to go; checked by Myhill-Nerode classes: 6.
Answer: minimum NFA 5 states, minimum DFA 6 states (including the dead state).
Finding RE from a DFA (Dec 2024). $q_1$ start, $q_1\xrightarrow{b}q_3$, $q_1\xrightarrow{a}q_2$, $q_2\xrightarrow{a}q_3$, $q_3$ loops on a. Equations: $q_1=\epsilon$, $q_2=q_1a$, $q_3=q_1b+q_2a+q_3a$, so $q_3=(b+aa)+q_3a$ and by Arden $q_3=(b+aa)a^*$.
Answer: RE $=(b+aa)a^*$.
Answer frame. For "obtain the RE": open with the language in words; write the RE part by part; justify each part with one sample string. For "construct an FA": open with the RE meaning; draw NFA then DFA; give the table; close with the finals. For "find RE for DFA": define RE, write state equations, use Arden.
Pitfall: Writing $(aaa+aaaaa)^*$ for "divisible by 3 or 5" wrongly accepts $a^8$; use $(aaa)^*+(aaaaa)^*$. Asked: [7 marks] (Nov 2019, May 2023, Dec 2025) Obtain the RE for (i) all strings over $\{a,b\}$ with exactly two a, (ii) $L=\{a^x\mid x$ divisible by 3 or 5$}$; also describe by RE: strings containing 1100, strings of 0's and 1's ending with 00, $\{\Lambda,a,aa,\ldots\}$, strings over $\{a,b\}$ ending with ab. Asked: [7 marks] (Nov 2023) Construct an equivalent FA for $(0+1)^*(00+11)(0+1)^*$. Asked: [6 marks] (Dec 2024) Define the regular expression; find the regular expression for the given DFA. Asked: [14 marks] (Jun 2025) For $(a+b)ab(a+b)$ calculate the minimum number of states in the equivalent NFA and DFA.
Arden's theorem
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. ==Arden's theorem: if $P$ and $Q$ are regular expressions and $P$ does not contain $\epsilon$, then $R=Q+RP$ has the unique solution $R=QP^*$.==
Proof. Put $R=QP^*$ on the right: $Q+QP^*P=Q(\epsilon+P^*P)=QP^*$, so it is a solution. Uniqueness: substituting $R=Q+RP$ into itself repeatedly gives $R=Q(\epsilon+P+\dots+P^{n})+RP^{n+1}$; a string of length $m$ cannot lie in $RP^{m+1}$ since $\epsilon\notin P$, so $R\subseteq QP^*$.
Steps.
Step 1: Check the DFA has no epsilon moves and one start state.
Step 2: For each state write q = (sum of incoming: previous state x symbol), adding epsilon for the start state.
Step 3: Solve the equations by substitution, using R = Q + RP => R = QP* for self-loops.
Step 4: The RE of the machine is the union of the expressions of all final states.
Example 1 (Nov 2022, Nov 2023). $A$ start, $C$ final: $A\xrightarrow{b}A$, $A\xrightarrow{a}B$, $B\xrightarrow{b}A$, $B\xrightarrow{a}C$, $C$ loops on $a,b$. $A=\epsilon+Ab+Bb$, $B=Aa$, $C=Ba+C(a+b)$. Then $A=\epsilon+A(b+ab)$ gives $A=(b+ab)^*$; $B=(b+ab)^*a$; $C=(b+ab)^*aa+C(a+b)$ gives $C=(b+ab)^*aa(a+b)^*$.
Answer: RE $=(b+ab)^*aa(a+b)^*$ (strings containing aa).
Example 2. $q_0$ loops on 1, $q_0\xrightarrow{0}q_1$, $q_1$ loops on 1, $q_1\xrightarrow{0}q_2$, $q_2\xrightarrow{0}q_1$, $q_2\xrightarrow{1}q_0$, final $q_2$. $q_0=\epsilon+q_01+q_21$, $q_1=q_00+q_11+q_20$, $q_2=q_10$. Then $q_1=q_00(1+00)^*$ and $q_0=(1+0(1+00)^*01)^*$.
Answer: RE $=(1+0(1+00)^*01)^*0(1+00)^*0$.
Pumping lemma. If $L$ is regular there is a length $n$ such that every $w\in L$ with $|w|\ge n$ splits as $w=xyz$ with $|xy|\le n$, $|y|\ge1$ and $xy^iz\in L$ for all $i\ge0$. It proves non-regularity by contradiction. Proof for $L=\{a^ib^i\mid i\ge1\}$. Assume regular with length $n$; take $w=a^nb^n$. Since $|xy|\le n$, $y=a^k$ with $k\ge1$. Then $xy^2z=a^{n+k}b^n\notin L$, a contradiction. So $L$ is not regular.
Answer frame. For Arden's theorem: state the theorem, give the proof, then solve one DFA. For a DFA-to-RE question: draw the equations, solve state by state, close with the final-state RE. For "Arden and pumping lemma": statement of each, then the proof of the first and the contradiction of the second.
Pitfall: Arden's theorem needs $\epsilon\notin P$; the RE of a DFA is the union of all final states, not just the last equation solved. Asked: [7 marks] (Nov 2022, Nov 2023) Compute the regular expression for the DFA shown. Asked: [7 marks] (May 2023) Explain Arden's theorem and Pumping Lemma. Asked: [7 marks] (Dec 2025) Explain regular expressions and Arden's theorem. Asked: [7 marks] (Jun 2020) State Pumping Lemma and show that $L=\{a^ib^i\mid i\ge1\}$ is not regular.
Meaning of union
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. ==The union of languages $L_1$ and $L_2$ is $L_1\cup L_2=\{w\mid w\in L_1\text{ or }w\in L_2\}$; in a regular expression it is written $r+s$.==
Key points.
- Regular languages are closed under union: a new start state with $\epsilon$-moves to both start states gives an NFA for $L_1\cup L_2$.
- With DFAs use the product construction, a pair of states accepted when either component is final.
- Example: $\{a\}\cup\{b\}=\{a,b\}$.
Intersection
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>The intersection $L_1\cap L_2$ is the set of strings in both languages; regular languages are closed under it, but context-free languages are not.</mark>
Key points.
- Proof for regular sets: complement and union are closed, so $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$ is regular by De Morgan.
- Direct proof by product construction: states $(p,q)$, $\delta((p,q),a)=(\delta_1(p,a),\delta_2(q,a))$, final when both $p\in F_1$ and $q\in F_2$.
- CFLs are not closed: $L_1=\{a^nb^nc^m\}$ and $L_2=\{a^mb^nc^n\}$ are context-free.
- But $L_1\cap L_2=\{a^nb^nc^n\mid n\ge0\}$ is not context-free (pumping lemma for CFL), so CFLs are not closed under intersection.
Answer frame. Open with the definition; for regular sets give De Morgan then the product construction; for CFL give the two languages, their intersection and the conclusion.
Asked: [7 marks] (Nov 2019) Prove that regular sets are closed over the intersection operation. Asked: [7 marks] (Jun 2020) Prove that CFL are not closed under intersection.
Concatenation
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. ==The concatenation of $L_1$ and $L_2$ is $L_1L_2=\{xy\mid x\in L_1,\ y\in L_2\}$; in a regular expression it is written $rs$.==
Key points.
- Regular languages are closed under concatenation: join the final states of the first automaton to the start state of the second by $\epsilon$-moves.
- Example: $\{a,ab\}\{b\}=\{ab,abb\}$; in general $L_1L_2\ne L_2L_1$.
- $L\{\epsilon\}=L$ and $L\emptyset=\emptyset$.
Closure
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. ==A class of languages is closed under an operation if applying the operation to members of the class always gives a language in the same class; the Kleene closure is $L^*=\bigcup_{i\ge0}L^i$.==
Key points.
- Union: $L_1\cup L_2$ is regular (new start state with $\epsilon$-moves to both).
- Concatenation: $L_1L_2$ is regular (final states of the first to the start of the second by $\epsilon$).
- Kleene star: $L^*$ is regular (new start and final state with $\epsilon$ loop-back from the old finals).
- Complement: swap final and non-final states of a complete DFA.
- Intersection: $\overline{\overline{L_1}\cup\overline{L_2}}$, or the product automaton.
- Difference $L_1-L_2=L_1\cap\overline{L_2}$, and reversal (reverse all edges, swap start and finals) are also regular.
- Homomorphism: replacing each symbol by a string keeps the language regular.
Answer frame. Open with the closure definition; list the properties in the order above, each with its one-line construction; close with "so regular languages form a Boolean algebra closed under all these operations".
Asked: [7 marks] (Nov 2019, Dec 2020) What do you mean by closure properties of regular languages? Define some important closure properties.
2 way DFA
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>A two-way DFA (2DFA) is a DFA $(Q,\Sigma,\delta,q_0,F)$ whose head can move left, right or stay: $\delta:Q\times(\Sigma\cup\{\vdash,\dashv\})\to Q\times\{L,R,S\}$, with the input between the end-markers $\vdash$ and $\dashv$.</mark>
Key points.
- The input sits on a tape between two end markers, and the head can go back and re-read symbols.
- The head never moves left of $\vdash$ or right of $\dashv$; the string is accepted when the machine reaches a final state on the right end-marker.
- Despite the extra head movement, 2DFAs accept exactly the regular languages (Shepherdson), though the equivalent one-way DFA may need exponentially more states.
| Basis | One-way DFA | Two-way DFA |
|---|---|---|
| Head move | right only | left, right or stay |
| $\delta$ | $Q\times\Sigma\to Q$ | $Q\times(\Sigma\cup\{\vdash,\dashv\})\to Q\times\{L,R,S\}$ |
| End-markers | not used | used |
| Symbols re-read | never | allowed |
| Power | regular languages | regular languages |
Answer frame. Open with the definition and tuple; draw the tape with the end-markers and the head; give the comparison table; close with the equivalence in power.
Asked: [7 marks] (Dec 2020, Jun 2025) Define two way finite automata. Asked: [7 marks] (Jun 2025) What is a 2-way DFA? How does it differ from a standard DFA in terms of tape head movement?
Last-minute revision
- DFA is $(Q,\Sigma,\delta,q_0,F)$ with $\delta:Q\times\Sigma\to Q$; NFA has $\delta:Q\times\Sigma\to2^Q$.
- A trap state is non-final and loops to itself on every symbol.
- Binary multiple of 3: $\delta(r,b)=(2r+b)\bmod3$; decimal multiple of 3: $(r+d)\bmod3$.
- Not ending in 01 needs 3 states; at most 3 a's needs 5 states (with dead).
- Subset construction: start is the $\epsilon$-closure of $q_0$, finals contain an NFA final; worst case $2^n$ states.
- Minimization: split final and non-final, refine until stable; merge equivalent states.
- Arden: $R=Q+RP\Rightarrow R=QP^*$ when $\epsilon\notin P$.
- $(a+b)ab(a+b)$: NFA 5 states, DFA 6 states.
- Regular languages are closed under union, concatenation, star, complement, intersection, difference, reversal and homomorphism; CFLs are not closed under intersection.
- 2DFA has head moves L, R, S but accepts only regular languages.
Memory hooks
- Dead state = drain: water goes in, never comes out.
- "Remainder as state": new remainder $=(2r+b)\bmod3$ for binary, $(r+d)\bmod 3$ for decimal.
- Subset construction: "one box per set, empty box = trap".
- Arden: "$R$ equals Q then any number of P" gives $QP^*$.
- Closure: complement swaps finals; De Morgan gives intersection.
Coverage checklist
- Non Deterministic Finite Automata (NDFA): Nov 2022 NFA mod 3, Dec 2025 DFA vs NFA.
- Deterministic finite automata machines: Nov 2019, May 2023, Dec 2020, Jun 2020 (two), Nov 2022, Nov 2023 (two), Dec 2024.
- conversion of NDFA to DFA: Nov 2022 / Dec 2025 convert NFA.
- minimization of automata machines: Dec 2024, Jun 2025.
- regular expression: Nov 2019 / May 2023 / Dec 2025 REs, Nov 2023 FA, Dec 2024 RE from DFA, Jun 2025 states count.
- Arden's theorem: Nov 2022 / Nov 2023 DFA to RE, May 2023, Dec 2025, Jun 2020 pumping lemma.
- Meaning of union: no past questions.
- intersection: Nov 2019, Jun 2020.
- concatenation: no past questions.
- closure: Nov 2019 / Dec 2020.
- 2 way DFA: Dec 2020 / Jun 2025, Jun 2025.