Back to the 2022 paper

Module 1: Introduction & Regular Languages

20222m

For a given Moore machine, given input = 101010, the output would be of length:

(i) |Input| + 1
(ii) |Input|
(iii) |Input| − 1
(iv) Cannot be predicted

Worked SolutionAI Assisted

Answer

Correct Option: (i) ∣Input∣+1|Input|+1

Explanation

Moore Machine: Output depends only on present state, and output is associated with state entry, including the initial state before any input is consumed.

  • For input length nn, the machine visits n+1n+1 states: q0q_0 (initial, no input) →a1q1→a2⋯→anqn\xrightarrow{a_1} q_1 \xrightarrow{a_2} \dots \xrightarrow{a_n} q_n.
  • Each state produces one output symbol λ(qi)\lambda(q_i).
  • Hence output string length = n+1n+1.

Mealy Machine contrast: Output depends on transition (state + input), so output length = ∣Input∣|Input| = nn (one per input symbol).

Given input 101010, ∣Input∣=6|Input|=6 → Moore output length = 77.

Final Answer

Moore machine output length is ∣Input∣+1|Input|+1 → Option (i).

Similar questions

Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.