Theory of Computation (CS-501) Unit 1 Notes

How unit 1 is examined

This unit covers automata as acceptors and translators, Moore and Mealy machines and converting one into the other; Mealy-Moore conversion, Mealy and Moore definitions and the Mealy-versus-Moore comparison carry the marks.

Examples 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">Not asked since 2022</span>

Definition. An automaton is an abstract machine that reads an input string one symbol at a time, moves between a finite set of states, and either accepts the string or produces an output string.

Key points.

A finite state machine has a finite memory, because its only memory is which state it is currently in.
A turnstile, a vending machine, a traffic light and a lift controller are everyday finite state machines.
A binary adder is a translator that reads bit pairs and outputs sum bits, while a "ends in 01" checker is an acceptor.
Compilers use finite automata in the lexical analyser to recognise tokens such as identifiers and numbers.

Finite Automata as a language acceptor and translator

Definition. A finite automaton is the 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$ where $Q$ is a finite set of states, $\Sigma$ the input alphabet, $\delta$ the transition function, $q_0\in Q$ the start state and $F\subseteq Q$ the set of final states. <mark>A finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ that either accepts a string by ending in a final state or translates it into an output string.</mark>

Key points.

$Q$ is the finite set of states, $\Sigma$ is the finite set of input symbols, and $\delta: Q\times\Sigma\to Q$ gives the next state for a state and an input symbol.
$q_0$ is the single start state and $F$ is the set of accepting (final) states, drawn as double circles.
As a language acceptor, the machine reads the whole string and accepts it if it halts in a state of $F$; the set of accepted strings is the language $L(M)=\{w\mid \delta^*(q_0,w)\in F\}$.
As a translator (transducer), the machine has no final states; it adds an output alphabet $\Delta$ and an output function, and writes an output string while it reads the input.
Moore and Mealy machines are the two translators: Moore attaches the output to the state, and Mealy attaches it to the transition.
Types of finite automata are DFA (exactly one move per state and symbol), NFA (several or no moves), $\epsilon$-NFA (moves without input) and the output machines Moore and Mealy.

Example. A DFA on $\{0,1\}$ with $F=\{q_1\}$ accepting strings that end in 1 is an acceptor; a machine that prints 1 for each input 1 and 0 for each input 0 is a translator.

Answer frame. Open with the 5-tuple; explain each component in one line; describe acceptor mode with $L(M)$ and one example; describe translator mode naming Moore and Mealy; list the types; close with "acceptors give yes/no, translators give an output string".

Asked: [7 marks] (Dec 2025) Explain finite automata as language acceptors and translators. Asked: [6 marks] (Dec 2024) Define finite-automata machine mathematically and explain its types.

Moore machines

Definition. A Moore machine is the 6-tuple $(Q,\Sigma,\Delta,\delta,\lambda,q_0)$ in which the output function $\lambda: Q\to\Delta$ depends only on the current state. <mark>In a Moore machine the output is associated with the state, so $\lambda(q)$ is printed whenever the machine enters $q$.</mark>

Key points.

The output is written inside the state as $q/output$, for example $q_1/1$.
The machine prints an output as soon as it enters a state, so it prints one output even for the empty input, the output of $q_0$.
For an input of length $n$ the output has length $n+1$.
Transitions carry only the input symbol, and the output does not change while the machine stays in a state.
A Moore machine usually needs more states than the equivalent Mealy machine, because each distinct output needs its own state.

Example. Moore machine that outputs 1 after an input 1 and 0 after an input 0 (states $q_0/0$, $q_1/1$):

State	Output	a=0	a=1
$q_0$	0	$q_0$	$q_1$
$q_1$	1	$q_0$	$q_1$

Input 1101 gives the output 0 1 1 0 1 (five symbols for four inputs).

Diagram. Comparison of the two models (Moore: output in the state; Mealy: output on the arc as input/output): <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 553 80" width="553" height="80" role="img" aria-label="Left pair Moore, right pair Mealy; a Moore state q/z carries its output z inside the circle"><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="M57.8,46.6 Q126,72 192.3,47.3" marker-end="url(#ah1)"/><path class="e" d="M194.2,33.4 Q126,8 59.7,32.7" marker-end="url(#ah1)"/><path class="e" d="M358.8,46.6 Q427,72 493.3,47.3" marker-end="url(#ah1)"/><path class="e" d="M495.2,33.4 Q427,8 360.7,32.7" marker-end="url(#ah1)"/><g class="wl"><rect x="115.9" y="50.5" width="19.2" height="18" rx="9"/><text class="t" x="125.5" y="59.5" dy=".35em" text-anchor="middle">a</text></g><g class="wl"><rect x="116.9" y="11.5" width="19.2" height="18" rx="9"/><text class="t" x="126.5" y="20.5" dy=".35em" text-anchor="middle">b</text></g><g class="wl"><rect x="409.7" y="50.5" width="33.6" height="18" rx="9"/><text class="t" x="426.5" y="59.5" dy=".35em" text-anchor="middle">a/1</text></g><g class="wl"><rect x="410.7" y="11.5" width="33.6" height="18" rx="9"/><text class="t" x="427.5" y="20.5" dy=".35em" text-anchor="middle">b/0</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">M0</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">M1</text><circle class="n" cx="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">Y0</text><circle class="n" cx="513" cy="40" r="18"/><text class="t" x="513" y="40" dy=".35em" text-anchor="middle">Y1</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Left pair Moore, right pair Mealy; a Moore state q/z carries its output z inside the circle</figcaption></figure>

Answer frame. Open with the two definitions; draw one Moore machine with $q/z$ states and one Mealy machine with $a/z$ arcs; then give the comparison table below; close with "Mealy reacts in the same step, Moore one step later".

Basis	Mealy machine	Moore machine
Output depends on	Present state and present input, $\lambda(q,a)$	Present state only, $\lambda(q)$
Output is written on	Transitions	States
Output length for input length $n$	$n$	$n+1$
Number of states	Fewer	More or equal
Response to input	Immediate, in the same clock	Delayed by one clock
Diagram label	$a/z$ on arcs	$q/z$ in circles

Asked: [7 marks] (Jun 2020, Jun 2025) Differentiate Mealy machine and Moore machine with diagram. Asked: [7 marks] (Jun 2025) Explain Moore and Mealy machines with examples. How do they differ in output behaviour?

Mealy machines

Definition. A Mealy machine is the 6-tuple $(Q,\Sigma,\Delta,\delta,\lambda,q_0)$ in which $\delta: Q\times\Sigma\to Q$ is the next-state function and $\lambda: Q\times\Sigma\to\Delta$ is the output function. <mark>In a Mealy machine the output is associated with the transition, so it depends on the present state and the present input symbol.</mark>

Key points.

Every arc is labelled $a/z$, meaning "on input $a$ print output $z$".
The output is produced during the transition, so the response to an input is immediate.
For an input string of length $n$, exactly $n$ output symbols are produced, and the empty input gives the empty output.
The machine has no final states, because it is a translator and not an acceptor.
It usually needs fewer states than the equivalent Moore machine, because one state can give different outputs for different inputs.
The same state can be entered with different outputs, which is why the Mealy-to-Moore conversion must split states.
Mealy machines model circuits whose output reacts to the input at once, such as serial adders and detectors.

Example (design). Mealy machine printing 1 for input 1 and 0 for input 0. One state is enough, since the output depends only on the current input:

State	Input 0	Input 1
$q_0$	$q_0$, 0	$q_0$, 1

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-02" viewBox="0 0 252 80" width="252" height="80" role="img" aria-label="Two-state view; the real machine is one state q0 with self-loops 0/0 and 1/1"><style>#dsfig-u1-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-02 .t{fill:#16181D;font-weight:500}#dsfig-u1-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-02 .dot{fill:#16181D}#dsfig-u1-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-02 .ah{fill:#454C5A}#dsfig-u1-02 .ah.hi{fill:#2340B8}#dsfig-u1-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-02 .e{stroke:#B1B7C3}html.dark #dsfig-u1-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-02 .t{fill:#E6E8ED}html.dark #dsfig-u1-02 .t.inv{fill:#0F1115}html.dark #dsfig-u1-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-02 .dot{fill:#E6E8ED}html.dark #dsfig-u1-02 .ann{fill:#8FA3FF}html.dark #dsfig-u1-02 .lbl{fill:#858D9C}html.dark #dsfig-u1-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-02 .ah{fill:#B1B7C3}html.dark #dsfig-u1-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" 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="ahh2" 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.8,46.6 Q126,72 192.3,47.3" marker-end="url(#ah2)"/><path class="e" d="M194.2,33.4 Q126,8 59.7,32.7" marker-end="url(#ah2)"/><g class="wl"><rect x="108.7" y="50.5" width="33.6" height="18" rx="9"/><text class="t" x="125.5" y="59.5" dy=".35em" text-anchor="middle">0/0</text></g><g class="wl"><rect x="109.7" y="11.5" width="33.6" height="18" rx="9"/><text class="t" x="126.5" y="20.5" dy=".35em" text-anchor="middle">1/1</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" 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">T</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Two-state view; the real machine is one state q0 with self-loops 0/0 and 1/1</figcaption></figure>

Trace for input 1011: outputs 1, 0, 1, 1, so the output is 1011, a copy of the input.

Answer frame. Open with "A Mealy machine is a finite automaton whose output depends on state and input"; draw the labelled diagram with $a/z$ arcs; for the design question write the table with one state, then the trace; for the theory question follow with the comparison table under Moore machines; close with the output-length rule $n$ against $n+1$.

Asked: [14 marks] (Nov 2019) Explain the Mealy and Moore Machines in brief. Also describe what are the differences between them. Asked: [7 marks] (Dec 2025) Design a Mealy machine that outputs 1 whenever the input symbol is '1', otherwise outputs 0.

Composite machine

Definition. A composite machine is a machine built by connecting two or more simpler machines, so that the output of one is fed as the input of the next, or they run in parallel.

Key points.

In a series (cascade) connection the output string of the first machine becomes the input string of the second, so the output alphabet of the first must be inside the input alphabet of the second.
In a parallel connection both machines read the same input, and the composite state is the pair of their states.
The state set of the composite machine is the product $Q_1\times Q_2$, so it is still a finite automaton.

Conversion from Mealy to Moore and vice versa

Definition. Two machines are equivalent when they give the same output string for every input string, apart from the extra first output of the Moore machine. <mark>A Mealy machine and a Moore machine are equivalent if, for every input, the Mealy output equals the Moore output with the first symbol (the output of $q_0$) removed.</mark>

Steps (Moore to Mealy).

Step 1: Keep the same states, inputs and transitions.
Step 2: For each transition p --a--> q, set the Mealy output of that arc to the Moore output of the destination state q.
Step 3: Write the Mealy table with an output on each arc and draw the diagram with labels a/z.
Step 4: Check with a sample string; the Mealy output equals the Moore output without its first symbol.

So $\lambda_{Mealy}(p,a)=\lambda_{Moore}(\delta(p,a))$. The number of states does not change.

Steps (Mealy to Moore).

Step 1: For every state q, list the different outputs on the arcs entering q.
Step 2: If q receives k different outputs, split it into k states q_z, one per output z; a state with one incoming output stays as it is.
Step 3: Send each arc to the split state whose output matches the arc output, and copy the outgoing arcs to every copy.
Step 4: The start state gets output 0 (or a chosen symbol), since Moore prints an output before any input.

An $n$-state Mealy machine gives at most $n\times|\Delta|$ Moore states.

Example 1 (Jun 2025, Moore to Mealy). States $A/0$, $B/1$; $A\to aB$, $A\to bA$, $B\to aA$, $B\to bB$. Output of each arc is the output of its destination:

State	a	b
$A$	$B$, 1	$A$, 0
$B$	$A$, 0	$B$, 1

Answer: Mealy arcs $A\xrightarrow{a/1}B$, $A\xrightarrow{b/0}A$, $B\xrightarrow{a/0}A$, $B\xrightarrow{b/1}B$. Check: input $ab$ gives Moore 0 1 1 and Mealy 1 1, which agree after dropping the first 0.

Example 2 (May 2023 / Jun 2025, 14 marks). (i) $q_0/0$: $a\to q_0$, $b\to q_1$; $q_1/1$: $a,b\to q_1$. (ii) $q_0/0$: $a,b\to q_1$; $q_1/1$: $a,b\to q_0$.

Machine	State	a	b
(i)	$q_0$	$q_0$, 0	$q_1$, 1
(i)	$q_1$	$q_1$, 1	$q_1$, 1
(ii)	$q_0$	$q_1$, 1	$q_1$, 1
(ii)	$q_1$	$q_0$, 0	$q_0$, 0

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-03" viewBox="0 0 338 80" width="338" height="80" role="img" aria-label="Mealy machine (ii); P is q0 (start) and Q is q1"><style>#dsfig-u1-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-03 .t{fill:#16181D;font-weight:500}#dsfig-u1-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-03 .dot{fill:#16181D}#dsfig-u1-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-03 .ah{fill:#454C5A}#dsfig-u1-03 .ah.hi{fill:#2340B8}#dsfig-u1-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-03 .e{stroke:#B1B7C3}html.dark #dsfig-u1-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-03 .t{fill:#E6E8ED}html.dark #dsfig-u1-03 .t.inv{fill:#0F1115}html.dark #dsfig-u1-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-03 .dot{fill:#E6E8ED}html.dark #dsfig-u1-03 .ann{fill:#8FA3FF}html.dark #dsfig-u1-03 .lbl{fill:#858D9C}html.dark #dsfig-u1-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-03 .ah{fill:#B1B7C3}html.dark #dsfig-u1-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" 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="ahh3" 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="M58.4,44.6 Q169,72 277.6,45.1" marker-end="url(#ah3)"/><path class="e" d="M279.6,35.4 Q169,8 60.4,34.9" marker-end="url(#ah3)"/><g class="wl"><rect x="145" y="49.4" width="47.1" height="18" rx="9"/><text class="t" x="168.5" y="58.4" dy=".35em" text-anchor="middle">a,b/1</text></g><g class="wl"><rect x="145.9" y="12.6" width="47.1" height="18" rx="9"/><text class="t" x="169.5" y="21.6" dy=".35em" text-anchor="middle">a,b/0</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Q</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Mealy machine (ii); P is q0 (start) and Q is q1</figcaption></figure>

Example 3 (Dec 2024). Moore: $q_0/0$, $q_1/0$, $q_2/1$; $q_0$: $a\to q_1$, $b\to q_0$; $q_1$: $a\to q_1$, $b\to q_2$; $q_2$: $a,b\to q_1$. Mealy output is the destination output:

State	a	b
$q_0$	$q_1$, 0	$q_0$, 0
$q_1$	$q_1$, 0	$q_2$, 1
$q_2$	$q_1$, 0	$q_1$, 0

Answer: the only arc printing 1 is $q_1\xrightarrow{b}q_2$, so this Mealy machine prints 1 exactly when a $b$ follows an $a$ (ab detected).

Example 4 (Jun 2020, Mealy to Moore). Arcs: $q_0$: $0\to q_0/0$, $1\to q_1/1$; $q_1$: $1\to q_0/0$, $0\to q_2/2$; $q_2$: $0\to q_1/1$, $1\to q_2/2$. Incoming outputs: $q_0$ receives only 0, $q_1$ only 1, $q_2$ only 2, so no state needs splitting. Each state takes its incoming output:

State	Output	0	1
$q_0$	0	$q_0$	$q_1$
$q_1$	1	$q_2$	$q_0$
$q_2$	2	$q_1$	$q_2$

Answer: Moore machine with states $q_0/0$ (start), $q_1/1$, $q_2/2$ and the table above.

Answer frame. Open with the conversion rule in one sentence; write the given machine as a table; apply the rule row by row (destination output for Moore to Mealy; splitting by incoming output for Mealy to Moore); draw the new machine with $a/z$ or $q/z$ labels; verify on one sample string; close with the equivalence statement. For the 8-mark paper put the six-row comparison table (under Moore machines) before the conversion.

Pitfall: Taking the output of the source state instead of the destination state for Mealy arcs, or forgetting to split a state that receives two different outputs.

Asked: [14 marks] (May 2023, Jun 2025) Convert the following Moore machine to Mealy: (i) $q_0/0$, $q_1/1$ machine (i); (ii) machine (ii). Asked: [8 marks] (Dec 2024) Write the differences between Mealy and Moore machine. Convert the given Moore machine into its equivalent Mealy machine. Asked: [7 marks] (Jun 2020) Construct Moore machine for the following Mealy machine. Asked: [7 marks] (Jun 2025) Convert the given Moore machine to a Mealy machine: states $\{A,B\}$, outputs $A/0$, $B/1$, transitions $A\to aB$, $A\to bA$, $B\to aA$, $B\to bB$.

Last-minute revision

A finite automaton is $(Q,\Sigma,\delta,q_0,F)$; an acceptor ends in $F$, a translator prints output.
Moore machine: 6-tuple with $\lambda: Q\to\Delta$, output on the state.
Mealy machine: 6-tuple with $\lambda: Q\times\Sigma\to\Delta$, output on the transition.
Output length is $n$ for Mealy and $n+1$ for Moore.
Mealy responds in the same step; Moore is one step delayed.
Moore to Mealy: arc output equals output of the destination state; state count unchanged.
Mealy to Moore: split each state by its distinct incoming outputs; at most $n\times|\Delta|$ states.
Moore start state prints its output before any input.
Composite machine: cascade feeds one output into the next input; states form $Q_1\times Q_2$.
Jun 2025 numerical: $A\xrightarrow{a/1}B$, $A\xrightarrow{b/0}A$, $B\xrightarrow{a/0}A$, $B\xrightarrow{b/1}B$.

Memory hooks

Moore = "More states, output on the State"; Mealy = "Moves carry output".
Moore gives $n+1$ outputs (the extra one is the start state's), Mealy gives $n$.
Moore to Mealy: "destination decides"; Mealy to Moore: "split by incoming output".
Acceptor says yes or no; translator writes a string.

Coverage checklist

Examples of automata machines: no past questions (definition and examples above).
Finite Automata as a language acceptor and translator: Dec 2025 (7 marks), Dec 2024 (6 marks).
Moore machines: Jun 2020 and Jun 2025 differentiate (7 marks), Jun 2025 explain (7 marks).
mealy machines: Nov 2019 (14 marks), Dec 2025 design (7 marks).
composite machine: no past questions.
Conversion from Mealy to Moore and vice versa: May 2023 and Jun 2025 (14 marks), Dec 2024 (8 marks), Jun 2020 (7 marks), Jun 2025 (7 marks).

Account

Theory of Computation (CS-501) - Unit 1 Short Notes

How unit 1 is examined

Examples of automata machines

Finite Automata as a language acceptor and translator

Moore machines

Mealy machines

Composite machine

Conversion from Mealy to Moore and vice versa

Last-minute revision

Memory hooks

Coverage checklist