A Mealy-machine option can look plausible until you trace the present state, current input, next state and edge output in the correct order. These 11 solved MCQs cover output equations, binary transducers, state tables, long-string traces, sequence detectors and hardware applications within the GATE CS Exam Preparation syllabus. Read an edge label as input/output, record one row per consumed symbol, append that edge's output, and only then update the state. KnowledgeGate has over 20 published questions in this Mealy Machine pool, so selected questions open on solved pages and the Mealy Machine PYQ Questions hub carries the wider set.
1. Mealy machine MCQs: the four-column trace to use every time
A Mealy transition output depends on (present state, current input); a Moore output belongs to a state. See Moore vs Mealy Machines: GATE Conversion and Minimization for comparison and conversion.
Record each symbol:
Present state | Input | Next state | Edge output |
|---|---|---|---|
|
|
|
|
For initial S0, use S0 --0/0--> S0, S0 --1/0--> S1, S1 --0/0--> S0 and S1 --1/1--> S1. Trace input 01101:
Present state | Input | Next state | Edge output |
|---|---|---|---|
S0 | 0 | S0 | 0 |
S0 | 1 | S1 | 0 |
S1 | 1 | S1 | 1 |
S1 | 0 | S0 | 0 |
S0 | 1 | S1 | 0 |
The output is 00100. Avoid output/input, next-state output selection, and lost overlapping prefixes.
2. Mealy machine MCQs 1-2: derive output logic and a binary transducer
Question 1, GATE 2021
Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1’s by a 0. Consider the following example.
Input sequence : 00100011000011100
Output sequence : 00000001000001100
A \(Mealy \ Machine\) is a state machine where both the next state and the output are functions of the present state and the current input. The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables \(s, \ t, \ b\) and \(y\) respectively. Assume the initial state of the \(Mealy \ Machine\) is 0.
What are the Boolean expressions corresponding to \(t\) and \(y\) in terms of \(s\) and \(b\)?
(a)
\(\begin{array}{l} t=s+b \\ y=sb \end{array} \\\)(b)
\(\begin{array}{l} t=b \\ y=sb \end{array} \\\)(c)
\(\begin{array}{l} t=b \\ y=s \overline{b} \end{array} \\\)(d)
\(\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}\)
Answer: (b), t=b and y=sb. Here s=1 means previous input 1. The state remembers current bit b, so t=b; only consecutive 1s survive, so y=sb.
|
|
|---|---|
|
|
|
|
|
|
|
|
The table reproduces 00100011000011100 -> 00000001000001100.
Question 2, GATE 2005
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.
!Two-state Mealy machine for two's complement
Which one of the following is TRUE?
(a) It computes 1\'s complement of the input number
(b) It computes 2\'s complement of the input number
(c) It increments the input number
(d) It decrements the input number
Answer: (b) It computes 2\'s complement of the input number. The left state uses 0/0 and 1/1; the right loops on 0/1 and 1/0. It copies trailing zeros and the first 1, then complements higher bits. For 00101100₂, LSB-first 0,0,1,1,0,1,0,0 emits 0,0,1,0,1,0,1,1, or 11010100₂ MSB-first.
3. Mealy machine MCQs 3-4: state-table paths and long output traces
Question 3, GATE 2009
Given the following state table of an FSM with two states A and B, one input and one output:
If the initial state is A=0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output = 1?
(a) 3
(b) 4
(c) 5
(d) 6
Answer: (a) 3. For AB=00,01,10,11, input 0 gives (00,1),(10,0),(01,0),(10,0); input 1 gives (01,0),(00,1),(01,1),(00,1). From 00, one input reaches 01 with output 0; the next reaches 10 with 0 or 00 with 1, so lengths 1 and 2 fail. Input 101 gives 00 --1/0--> 01 --0/0--> 10 --1/1--> 01, proving 3 is minimal.
Question 4
Consider the Mealy machine with 𝙲 = {0, 1} and Δ = {a, b}.
!Three-state Mealy machine over inputs 0 and 1 with outputs a and b
Find the output generated by the machine if the input string is 1011011110
(a) aaabaabbba
(b) aabbaabbaa
(c) ababaabbba
(d) aaabaababa
From initial q0, use 0/a to q0, 1/a to q1; from q1, 1/b to q1, 0/a to q2; from q2, 1/a to q1, 0/b to q0.
Step | Input | Present state | Edge | Next state | Output |
|---|---|---|---|---|---|
1 | 1 | q0 | 1/a | q1 | a |
2 | 0 | q1 | 0/a | q2 | a |
3 | 1 | q2 | 1/a | q1 | a |
4 | 1 | q1 | 1/b | q1 | b |
5 | 0 | q1 | 0/a | q2 | a |
6 | 1 | q2 | 1/a | q1 | a |
7 | 1 | q1 | 1/b | q1 | b |
8 | 1 | q1 | 1/b | q1 | b |
9 | 1 | q1 | 1/b | q1 | b |
10 | 0 | q1 | 0/a | q2 | a |
Answer: (a) aaabaabbba. Concatenate one output per row before updating the state.
4. Mealy machine MCQs 5-6: model properties and overlapping sequence detection
Question 5
Analyze the following statements about Mealy and Moore models:
In a Mealy machine, the output is determined solely by the current state of the memory elements.
In a Moore machine, the output may vary during the clock cycle based on external input changes.
A Mealy machine requires fewer states than a Moore machine for the same logic implementation.
Identify the incorrect statements:
(a) 1 and 2 only
(b) 1 and 3 only
(c) 1, 2, and 3
(d) 2 and 3 only
Answer: (a) 1 and 2 only. Statement 1 reverses the models: Mealy output uses state and input. Statement 2 is wrong because Moore output is fixed by state. Statement 3 correctly states the state-count advantage.
Question 6
A Mealy machine is designed to output '1' for every occurrence of the substring "101" and '0' otherwise. If the input string is "110101110", what will be the output string?
(a) 001001000
(b) 000101000
(c) 000001000
(d) 001000100
Answer: (b) 000101000. In 110101110, 101 ends at positions 4 (input[2..4]) and 6 (input[4..6]), giving 0 0 0 1 0 1 0 0 0. Position 4 starts the second occurrence, so an empty-prefix reset misses the overlap.
5. Mealy machine MCQs 7-8: finite-state arithmetic and edge-output meaning
Question 7, UPPSC Polytechnic Lecturer 2022
An FSM can be used to add two given numbers (integers). This remark is —
(a) True
(b) False
(c) Maybe True
(d) None of the above
Answer: (a) True. A bit-serial adder needs only carry states C0 and C1. In C0, 11 emits 0 and enters C1; there, 01 emits 0 and stays, while 00 emits 1 and returns to C0. The carry state stores the required history.
Question 8, GATE 2002
The finite state machine described by the following state diagram with A as starting state, where an arc label is x / y and x stands for 1-bit input and y stands for 2-bit output
!Three-state machine with one-bit inputs and two-bit outputs
(a) Outputs the sum of the present and the previous bits of the input
(b) Outputs 01 whenever the input sequence contains 11
(c) Outputs 00 whenever the input sequence contains 10
(d) None of these
Answer: (a) Outputs the sum of the present and the previous bits of the input. Edges from A are 0/00 to A, 1/01 to B; from B, 0/01 to A, 1/10 to C; from C, 0/01 to A, 1/10 to C. They encode 0+0=00, 1+0=01, 0+1=01, 1+1=10. With previous bit 0, 0110 emits 00,01,10,01.
6. Mealy machine MCQs 9-11: hardware use, diagram identification and output dependency
Question 9, Beltron Programmer 2025
Which hardware component is typically designed using finite automata principles?
(a) Sequential circuit controllers
(b) Floating-point unit
(c) Arithmetic Logic Unit (ALU)
(d) Cache memory
Answer: (a) Sequential circuit controllers. A controller chooses its next state from current state and inputs. In Idle -> Load -> Run -> Idle, start=1, loaded=1 and done=1 trigger moves. Datapaths and caches can contain FSM control, but are not the best answer.
Question 10, CDAC CCAT 2017
What does the diagram given below represent?
!Two-state transition diagram with input-output labels on every edge
(a) State Diagram
(b) Mealy Machine
(c) Moore Machine
(d) None of the above
Answer: (b) Mealy Machine. From Si, 0/0 goes to S0 and 1/0 to S1; S0 loops on 0/0 and uses 1/1 to S1; S1 loops on 1/0 and uses 0/1 to S0. Transition input/output pairs identify Mealy. Moore outputs appear on state labels such as S0/0.
Question 11, TPSC 2026
On what does the output of a Mealy machine depend?
(a) Only present state
(b) Only input
(c) current input + Present state
(d) Only clock
Answer: (c) current input + Present state. Formally, z=lambda(q,x). In the calibration machine, input 1 emits 0 in S0 but 1 in S1, so neither variable alone suffices. The clock controls state-change timing, not the output variables.
7. Mealy machine MCQ traps: the short version and next practice step
Trap | Evidence to reconstruct |
|---|---|
Present versus next state | Q1's |
LSB-first reading | Q2's |
Minimal path proof | Q3's input |
One output per consumed symbol | Q4's ten-symbol trace |
Overlap retention | Q6's detections ending at positions 4 and 6 |
Edge-label order | Q8's |
Hide the options and redo Q1, Q3, Q4, Q6 and Q8. Rebuild four rows, three edges, ten letters, nine indexed positions and four binary-sum cases. Repair any differing intermediate value before rechecking an option.
Continue with Finite Automata MCQs: 10 Solved DFA and NFA (GATE). For a sequenced Theory of Computation path, use GATE Guidance by Sanchit Sir.
The short version is simple: write the present state and current input first, read the matching edge's output, append exactly one output symbol, and only then move to the next state.
