Mealy and Moore machines

1. State the Myhill–Nerode theorem in one line.
   Stuck? Peek at 1.3.3 Myhill–Nerode theorem

   • x ≡_L y ⇔ ∀z: xz ∈ L ⇔ yz ∈ L. Right-invariant equivalence.
   • L regular ⇔ finite index; index = #states of minimal DFA (incl. dead class).
   • Infinitely many pairwise distinguishable strings ⇒ not regular. aⁿbⁿ: strings aⁱ separated by bⁱ.

   Read lesson 1.3.3

2. Minimal DFA states for “2nd symbol from the end is 1”?
   Stuck? Peek at 1.2.3 Subset construction and the 2ⁿ blow-up

   • Subset construction: start {q₀} (or ECLOSE(q₀)); δ(S,a) = ⋃ δ(q,a) (then ECLOSE); accept iff S ∩ F ≠ ∅; ∅ = dead state.
   • ≤ 2ⁿ states; count only reachable sets.
   • ε-removal: δ'(q,a) = ECLOSE(δ(ECLOSE(q), a)); F' = {q : ECLOSE(q) ∩ F ≠ ∅}.
   • k-th from end is 1: NFA k+1, DFA 2ᵏ. k-th from start: DFA k+2.
   • DFA ≡ NFA ≡ ε-NFA in power.

   Read lesson 1.2.3

3. How many states does a product of 3- and 4-state DFAs have at most?
   Stuck? Peek at 1.1.4 Product construction and complement

   • Product: states Q₁×Q₂, δ((p,q),a) = (δ₁(p,a), δ₂(q,a)), start (s₁,s₂).
   • ∩: F₁×F₂. ∪: F₁×Q₂ ∪ Q₁×F₂. −: F₁×(Q₂−F₂). ≤ |Q₁|·|Q₂| states.
   • Complement: complete the DFA (add dead state), swap F ↔ Q−F; same state count.
   • Regular languages closed under ∪, ∩, −, complement.

   Read lesson 1.1.4

A traffic-light controller doesn’t answer yes or no — it outputs a colour at every moment. A serial adder outputs one bit for every pair of input bits. These are finite-state machines that translate an input string into an output string. GATE gives this topic low weight, but the two output conventions are easy marks.

A machine prints one output symbol every time it is in a state (including the start state). For an input of length 5, how long is the output?

Prediction check

Answer: 6. It visits 6 states (start + one after each symbol) — the same “moments” count as the pigeonhole lesson (0.2.4). That is a Moore machine.

Moore machine

Mealy machine

Neither machine has accepting states; they compute outputs, not yes/no.

Equivalence and conversion

A Moore and a Mealy machine are considered equivalent if their outputs agree after ignoring the Moore machine’s initial output λ(q₀).

• Moore → Mealy: same states; λ'(q, a) = λ(δ(q, a)) (output the label of the state you enter). States: same number.
• Mealy → Moore: split each state q into copies (q, o) for each output o of transitions entering q. At most |Q| · |Δ| states (plus possibly one extra copy for the start state).

Typical machines

• Residue mod 3 of a binary number (Moore): states r0, r1, r2 output 0, 1, 2.
• 1’s complement (Mealy): one state, output 1 on input 0 and 0 on input 1.
• Detect “11” (Mealy): output 1 on a transition that completes 11.

Putting it together

• Moore: output per state, n + 1 symbols. Mealy: output per transition, n symbols.
• Moore → Mealy keeps the states; Mealy → Moore may need |Q|·|Δ|.
• Neither has accepting states — they translate rather than decide.

Moore: residue mod 3 (state/output)          input 101 (=5):
        0     1                              r0/0 ─1→ r1/1 ─0→ r2/2 ─1→ r2/2
→ r0/0  r0    r1                             output 0 1 2 2   (length 3+1 = 4)
  r1/1  r2    r0                             last output 2 = 5 mod 3 ✓
  r2/2  r1    r2

Mealy: output 1 when the last two inputs are 11
 state  on 0      on 1                       input 0111:
 A      A / 0     B / 0                      A ─0/0→ A ─1/0→ B ─1/1→ B ─1/1→ B
 B      A / 0     B / 1                      output 0 0 1 1   (length 4)

Phase 1 complete. Finite automata in every flavour: DFA, NFA, ε-NFA, minimal DFA, and output machines. Phase 2 gives regular languages a second face: algebraic formulas called regular expressions — the thing behind search patterns in every editor.

1. NAT

   A Moore machine processes an input of length 12. Output length?

   Write your answer before opening the key.

2. MCQ

   In a Mealy machine the output function is:

   1. λ : Q → Δ
   2. λ : Q × Σ → Δ
   3. λ : Σ → Δ
   4. λ : Δ → Q
3. MSQ

   Which are true?

   1. Moore → Mealy needs no extra states
   2. Mealy and Moore machines have accepting states
   3. Mealy → Moore may need up to |Q|·|Δ| states
   4. A Moore machine’s output depends only on the current state
4. NAT

   Using the residue-mod-3 Moore machine, what is the last output symbol for input 1101?

   Write your answer before opening the key.

• transducer (output machine)
• output alphabet Δ
• Moore machine (output on states)
• Mealy machine (output on transitions)
• Moore ↔ Mealy conversion

1. Moore vs Mealy output length for input length n?
   Reveal answer

   Moore n + 1; Mealy n.
2. Max Moore states when converting a Mealy machine?
   Reveal answer

   |Q| · |Δ| (standard answer).
3. Moore output function type?
   Reveal answer

   λ : Q → Δ