How unit 1 is examined
This unit covers the basics of sets, proofs, languages and automata; the marks come from Mealy and Moore machines (a 14-mark mod-5 design), the Mealy to Moore conversion, induction proofs, and the acceptor and translator idea.
Review of Sets
<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. A set is a well-defined collection of distinct objects called elements; $x \in A$ means $x$ belongs to $A$.
Key points.
- $A \subseteq B$ means every element of $A$ is in $B$; a set with $n$ elements has $2^n$ subsets.
- Union $A \cup B$, intersection $A \cap B$, difference $A - B$ and complement $\overline{A}$ are the basic operations, and $\emptyset$ is the empty set.
- De Morgan's laws are $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$.
Mathematical formal proofs including proof by induction and by contradiction
<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">Low weight</span>
Definition. <mark>Mathematical induction proves a statement $P(n)$ for all $n \ge 1$ by proving a base case $P(1)$ and an inductive step $P(k) \Rightarrow P(k+1)$.</mark>
Key points.
- Basis: verify $P(1)$ directly.
- Inductive step: assume $P(k)$ (the hypothesis) and derive $P(k+1)$ by algebra.
- Proof by contradiction assumes the statement is false and derives an impossibility, so the statement must be true.
Example. Prove $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ (the paper writes the last term of the series as $3^3$, a misprint for $3^2$).
- Base case $n=1$: LHS $=1$, RHS $=\frac{1\cdot2\cdot3}{6}=1$, so $P(1)$ holds.
- Assume $P(k)$: $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$.
- For $n=k+1$, add $(k+1)^2$ to both sides:
$$\frac{k(k+1)(2k+1)}{6}+(k+1)^2=\frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}=\frac{(k+1)(2k^2+7k+6)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$$
- This is $\frac{n(n+1)(2n+1)}{6}$ with $n=k+1$, so $P(k+1)$ holds. By induction the formula is true for all $n \ge 1$.
Asked: [7 marks] (Nov 2023) Prove that $1^2 + 2^2 + 3^2 + \dots + n^2 = \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ using mathematical induction.
Introduction to languages, grammars and automata
<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. A language is a set of strings over an alphabet, a grammar is a set of rules that generates the strings of a language, and an automaton is an abstract machine that accepts or rejects strings.
Key points.
- A grammar generates a language while an automaton recognises it.
- Automata theory studies what each class of machine can compute.
- The Chomsky hierarchy links grammar types to machines: regular to finite automata, context-free to PDA, and unrestricted to Turing machines.
Alphabet
<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. An alphabet $\Sigma$ is a finite, non-empty set of symbols, for example $\Sigma=\{0,1\}$.
Key points.
- A string is a finite sequence of symbols from $\Sigma$, and its length is $|w|$.
- The empty string $\varepsilon$ has length 0.
- $\Sigma^*$ is the set of all strings over $\Sigma$ including $\varepsilon$, and $\Sigma^+=\Sigma^*-\{\varepsilon\}$.
- A language is any subset of $\Sigma^*$.
Representation of language and grammar
<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. A grammar is $G=(V,T,P,S)$: variables $V$, terminals $T$, productions $P$ and start symbol $S$.
Key points.
- A language is represented either by set notation such as $\{0^n1^n \mid n\ge1\}$ or by a grammar, a regular expression or an automaton.
- A production $\alpha \to \beta$ rewrites $\alpha$ as $\beta$, and $L(G)$ is the set of terminal strings derived from $S$.
- Example: $S \to 0S1 \mid 01$ generates $\{0^n1^n \mid n\ge1\}$.
Types of Automata
<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. Automata are classified by their memory: the more memory, the more languages the machine accepts.
Key points.
- A finite automaton (FA, DFA or NFA) has no memory beyond its state and accepts regular languages.
- A pushdown automaton (PDA) has a stack and accepts context-free languages.
- A linear bounded automaton (LBA) has tape limited to the input length and accepts context-sensitive languages.
- A Turing machine (TM) has an unbounded tape and accepts recursively enumerable languages.
Finite Automata as a language acceptor and translator
<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">Low weight</span>
Definition. An acceptor is a machine that only says accept or reject for an input string, and a translator is a machine that produces an output string for the input.
Key points.
- The types of automata are FA, PDA, LBA and TM (see Types of Automata).
- As an acceptor, a DFA $(Q,\Sigma,\delta,q_0,F)$ accepts $w$ if $\delta^*(q_0,w)\in F$, so $L(M)=\{w \mid \delta^*(q_0,w)\in F\}$. Example: a DFA over $\{0,1\}$ accepting strings ending in 1.
- As a translator, the FA is given an output alphabet $\Delta$ and an output function $\lambda$, so every input symbol produces an output symbol; this is the Moore machine (output on state) or the Mealy machine (output on transition).
- Both uses are proved by construction: the same states and transitions either mark final states or print outputs, and a Mealy machine gives $|output|=|input|$ while a Moore machine gives $|input|+1$.
Answer frame. Open with the list of automata and the memory each has; define acceptor and translator; show the DFA 5-tuple, then the Mealy 6-tuple; give one example of each; close that a finite automaton is both.
Asked: [7 marks] (Nov 2023) Explain the types of Automata and prove that the Finite Automata as a language acceptor and translator.
Moore machines and mealy 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. <mark>A Mealy machine is a 6-tuple $(Q,\Sigma,\Delta,\delta,\lambda,q_0)$ whose output depends on the current state and input, $\lambda:Q\times\Sigma\to\Delta$; a Moore machine has the same tuple but its output depends only on the state, $\lambda:Q\to\Delta$.</mark>
Key points.
- Both machines have no final states, because they translate strings instead of accepting them.
- In a Mealy machine the output is written on the transition as input/output, so a string of length $n$ gives $n$ outputs.
- In a Moore machine the output is written inside the state, so a string of length $n$ gives $n+1$ outputs, the first being the start-state output.
- Every Mealy machine has an equivalent Moore machine and vice versa, ignoring the Moore start output.
- The Mealy machine usually needs fewer states and reacts in the same clock cycle; the Moore output changes only after the state changes and is more stable.
- Applications: Mealy in serial adders, sequence detectors and protocol converters; Moore in traffic lights, vending machines and counters.
Example (Nov 2022). Mealy machine for the residue mod 5 of a binary number. Let the state be the residue $r\in\{0,1,2,3,4\}$. Reading bit $b$ turns value $v$ into $2v+b$, so the next residue is $(2r+b)\bmod 5$ and the output is that new residue; start at $r_0$.
| State | Input 0 | Input 1 |
|---|---|---|
| r0 | r0 / 0 | r1 / 1 |
| r1 | r2 / 2 | r3 / 3 |
| r2 | r4 / 4 | r0 / 0 |
| r3 | r1 / 1 | r2 / 2 |
| r4 | r3 / 3 | r4 / 4 |
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Mod-5 Mealy machine; label is input/output, states R0-R4 are residues 0-4. Self-loops R0 on 0/0 and R4 on 1/4 not drawn."><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" 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="ahh1" 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="M55.8,115.5 L151.5,51.6" marker-end="url(#ah1)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah1)"/><path class="e" d="M162.4,57.8 Q137,126 161.7,192.3" marker-end="url(#ah1)"/><path class="e" d="M298,59 L298,191" marker-end="url(#ah1)"/><path class="e" d="M280,46 L59.9,119.4" marker-end="url(#ah1)"/><path class="e" d="M175.6,194.2 Q201,126 176.3,59.7" marker-end="url(#ah1)"/><path class="e" d="M180.4,196.8 L285.4,56.8" marker-end="url(#ah1)"/><path class="e" d="M279,212 L190,212" marker-end="url(#ah1)"/><g class="wl"><rect x="87.7" y="74" width="33.6" height="18" rx="9"/><text class="t" x="104.5" y="83" dy=".35em" text-anchor="middle">1/1</text></g><g class="wl"><rect x="216.7" y="31" width="33.6" height="18" rx="9"/><text class="t" x="233.5" y="40" dy=".35em" text-anchor="middle">0/2</text></g><g class="wl"><rect x="132.7" y="116.5" width="33.6" height="18" rx="9"/><text class="t" x="149.5" y="125.5" dy=".35em" text-anchor="middle">1/3</text></g><g class="wl"><rect x="281.2" y="117" width="33.6" height="18" rx="9"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">0/4</text></g><g class="wl"><rect x="152.2" y="74" width="33.6" height="18" rx="9"/><text class="t" x="169" y="83" dy=".35em" text-anchor="middle">1/0</text></g><g class="wl"><rect x="171.7" y="117.5" width="33.6" height="18" rx="9"/><text class="t" x="188.5" y="126.5" dy=".35em" text-anchor="middle">0/1</text></g><g class="wl"><rect x="216.7" y="117" width="33.6" height="18" rx="9"/><text class="t" x="233.5" y="126" dy=".35em" text-anchor="middle">1/2</text></g><g class="wl"><rect x="216.7" y="203" width="33.6" height="18" rx="9"/><text class="t" x="233.5" y="212" dy=".35em" text-anchor="middle">0/3</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">R0</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">R1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">R2</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">R3</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">R4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Mod-5 Mealy machine; label is input/output, states R0-R4 are residues 0-4. Self-loops R0 on 0/0 and R4 on 1/4 not drawn.</figcaption></figure>
Check: $1101_2=13$: residues 1, 3, 1, 3 and $13 \bmod 5=3$.
Pitfall: A Moore machine outputs one extra symbol for the start state; forgetting it gives the wrong output length.
Answer frame. Open with the Mealy definition; draw the 5-state diagram with loops; give the transition table; then develop points 1-6; close with the check on a sample string.
Asked: [14 marks] (Nov 2022) Construct a Mealy machine for binary language to determine the residue modulo 5.
composite machine
<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. A composite machine is a larger machine built by joining smaller machines so that the output of one feeds the input of the next.
Key points.
- Machines can be connected in series (cascade) or in parallel.
- The state of the composite machine is the tuple of the component states, so its state count is the product.
- Real sequential circuits are built as composite machines.
Conversion from Mealy to Moore and vice versa
<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">Low weight</span>
Definition. <mark>Mealy to Moore conversion splits each Mealy state into one Moore state for each distinct output that enters it.</mark>
Steps.
Step 1: For each state q, list the distinct outputs on transitions entering q.
Step 2: Make one copy of q per output (q with output Z).
Step 3: Redirect each transition to the copy that matches its output.
Step 4: Copy the outgoing transitions of q to every copy.
Step 5: A state with no incoming transition (the start) keeps one copy.
Example (Nov 2023). q1 has no incoming edge; q2 receives Z1 and Z2, so it splits into q2a (Z1) and q2b (Z2); q3 splits likewise into q3a (Z1) and q3b (Z2). Start state q1 is given output Z1.
| Moore state | 0 | 1 | Output |
|---|---|---|---|
| q1 | q2a | q3a | Z1 |
| q2a | q2b | q3a | Z1 |
| q2b | q2b | q3a | Z2 |
| q3a | q2a | q3b | Z1 |
| q3b | q2a | q3b | Z2 |
Moore to Mealy is easier: each transition takes the output of its target state, so the states stay the same.
Answer frame. Define both machines and the difference in output; state purpose and applications (see the Moore and Mealy section); then the steps and the table.
Asked: [7 marks] (Nov 2023) Explain the purpose of Mealy machine and Moore machine. Write application area of Mealy and Moore machine. Convert the following Mealy machine into Moore Machine (q1 start; q1 -0/Z1-> q2, q1 -1/Z1-> q3, q3 -0/Z1-> q2, q2 -1/Z1-> q3, q2 self-loop 0/Z2, q3 self-loop 1/Z2).
Last-minute revision
- Set with $n$ elements has $2^n$ subsets; De Morgan: $\overline{A\cup B}=\overline{A}\cap\overline{B}$.
- Induction: base case, assume $P(k)$, prove $P(k+1)$, conclude.
- $\sum i^2 = \frac{n(n+1)(2n+1)}{6}$.
- $\Sigma$ is a finite non-empty alphabet; $\Sigma^*$ contains $\varepsilon$.
- Machines by memory: FA (none), PDA (stack), LBA (bounded tape), TM (unbounded tape).
- Mealy output on transition, $n$ outputs; Moore output on state, $n+1$ outputs.
- Mod-5 machine: next residue $=(2r+b)\bmod 5$, output is the residue.
- Mealy to Moore: split each state by incoming output; the number of states can grow up to $|Q|\times|\Delta|$.
- Moore to Mealy: same states, output of the target state moves to the transition.
Memory hooks
- Mealy = Move (output on the arrow); Moore = Mood (output in the state).
- Doubling rule for binary residues: $2r+b$.
- Memory ladder: none, stack, bounded tape, tape (FA, PDA, LBA, TM).
- Split by the outputs coming in.
Coverage checklist
- Review of Sets: definition, subsets, De Morgan.
- Mathematical formal proofs including proof by induction and by contradiction: Nov 2023 induction on $\sum i^2$.
- Introduction to languages, grammars and automata: definitions and hierarchy link.
- Alphabet: $\Sigma$, strings, $\Sigma^*$.
- Representation of language and grammar: set notation, $G=(V,T,P,S)$.
- Types of Automata: FA, PDA, LBA, TM.
- Finite Automata as a language acceptor and translator: Nov 2023 types and acceptor/translator.
- Moore machines and mealy machines: Nov 2022 mod-5 Mealy machine.
- composite machine: series and parallel connection.
- Conversion from Mealy to Moore and vice versa: Nov 2023 purpose, applications, conversion.