Reduce a seven-state Mealy machine to at most four states by merging equivalent states, without changing what it does.
Hardware context: A protocol block drawn with more states than it needs, under an area review. Reduce a seven-state Mealy machine to four states with the same behaviour.
A protocol block was drawn with seven states by three people. The area review says it needs at most four, and the behaviour must not change on any input stream.
This is an Optimize problem with no logic to write. Write a state table as constants. The starter holds the original table: it is correct, but it uses seven states.
The check runs your table and the original from reset on every input stream of up to 14 bits. It compares z on every step, then counts your states.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
question | 8 | input of each check |
Full specification
| State | next if x = 0 | next if x = 1 | z if x = 0 | z if x = 1 |
|---|---|---|---|---|
| S0 | S2 | S5 | 0 | 0 |
| S1 | S3 | S3 | 0 | 0 |
| S2 | S6 | S1 | 1 | 1 |
| S3 | S3 | S4 | 1 | 1 |
| S4 | S3 | S2 | 0 | 0 |
| S5 | S3 | S2 | 1 | 1 |
| S6 | S2 | S4 | 1 | 1 |
Your table may number its states as you like, but S0 must be the reset state. Rows from N up are ignored.
Examples
Example 1
The Table Is Well Formed- Input
N from 1 to 7; every used row names a used state
- Output
bad_table = no, rows = 0
The first check reads N and every used row. A next state at or above N, or a z that is not 0 or 1, fails here.
Example 2
Same z on Every Short Stream- Input
all 30 streams of 1 to 4 bits, from reset
- Output
differs = no
Your table and the original run from reset on all 30 streams of 1 to 4 bits. On a difference the result shows the first stream that tells them apart.
Example 3
Same z on Every Stream up to 8 Bits- Input
all streams of 1 to 8 bits, from reset
- Output
differs = no
The same comparison on longer streams. A wrong merge often shows only after two or three inputs.
Constraints and Contract
- Keep the module name answer and the names of the constants.
- N is 1 to 7; next states are below N; every z is 0 or 1.
Hints
Hint 1
Start with one class per output row: (z on 0, z on 1). Then split a class when two of its states go to different classes on some input.
Hint 2
Repeat until a pass splits nothing. One pair that agrees on outputs and on the first split still falls apart on the second pass.
Hint 3
Number the final classes, put the class of S0 first, and copy each class's row with its next states renamed.
What the grader checks: Your table and the original run from reset on every input stream of 1 to 14 bits. z is compared on each step. Then N must be at most 4. Any numbering of the states passes.
5 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 2 steps and the final capstone