1. Finite State Machines
Definition – Finite State Machine (FSM)
An FSM consists of three sets and two functions:
| Element | Meaning |
|---|---|
| Set of input combinations | |
| Set of output combinations | |
| Set of states | |
| Next-state function | |
| Output function: for Moore, for Mealy |
State diagrams and state tables are just two ways of representing an FSM.
2. Limits of Traditional Diagrams and Tables
Traditional representations require:
- enumerating all input combinations for each state (next states and Mealy outputs),
- enumerating all output combinations per state (Moore) or per input–state pair (Mealy),
- Mealy outputs written only on arcs.
Fine for few inputs/outputs; intractable for many. The State Machine Diagram (SMD) solves this — it has the flexibility of an ASM chart without its notational constraints.
3. The State Machine Diagram (SMD)
Definitions – Conditions
| Term | Definition |
|---|---|
| Input condition | Boolean expression of inputs, evaluates to 0 or 1 |
| Transition condition (TC) | Input condition on an arc; arc taken when TC = 1 |
| Output condition (OC) | Input condition that, when 1, makes an output action occur |
| Unconditional transition | Arc with no TC (or TC = 1) |
| Conditional transition | Arc with one or more TCs; taken if any is 1 |
Definitions – Output action types
| Type | Attached to | Occurs when |
|---|---|---|
| Moore (unconditional) | State | Always while in the state |
| TCI Mealy (transition-condition-independent) | State, written OC/action | OC = 1 |
| TCD Mealy (transition-condition-dependent) | Arc’s TC | That TC = 1 |
| TCOD Mealy (transition-and-output-condition-dependent) | Arc’s TC, written OC/action | TC = 1 and OC = 1 |
Moore and TCI actions attached to a state apply on all transitions leaving it.
Output action notation
- Single variable: writing
Zmeans Z = 1 there; Z = 0 elsewhere (unless a default says otherwise). - Vector: write
Z = value; a default value must be specified (may include don’t-cares). - Register transfers: allowed as outputs (useful for datapath control).
⚠️ Only Moore outputs fit a pure Moore machine. TCD alone = classic Mealy. Mixing types is optional — it just simplifies the diagram.
Example – Same outputs, four styles
Inputs A, B, C; outputs Y, Z; defaults Y = 0, Z = 0. From S0: → S1, → S2.
| Style | Notation in S0 | Result |
|---|---|---|
| Moore | Y, Z on S0 | Y = Z = 1 whenever in S0 |
| TCI | A/Y, B/Z on S0 | Y = A, Z = B in S0 |
| TCD | A·B/Y and (A'+B')/Z on arcs | Y = 1 on the S1 arc, Z = 1 on the S2 arc |
| TCOD | C/Y on each arc | Y = 1 if that arc is taken and C = 1 |
stateDiagram-v2 direction LR S0 --> S1 : A·B / Y S0 --> S2 : (A'+B') / Z note left of S0 : TCD example — output on the arc whose TC = 1
4. Constraint Checking
Transition-condition constraints (for each state )
- Mutually exclusive: for every pair of TCs to distinct next states, .
- All-inclusive: (some transition always defined).
Output-condition constraints (for each state )
- For actions giving the same output variable different values, their OCs must be mutually exclusive: .
- For every output variable, the OCs (including the default) must cover all input combinations: .
For TCD and TCOD actions, the TC is part of the effective output condition.
Example – Checking a 4-state SMD
Defaults Y = 0, Z = 0.
| State | Transitions | ||
|---|---|---|---|
| S0 | → S1, → S2 | ✅ | ✅ |
| S1 | → S2, → S3 | ✅ | ✅ |
| S2 | → S3, → S0 | ✅ | ✅ |
| S3 | → S0, → S1 | ✅ | ✅ |
Output constraints are satisfied for all four states (with defaults).
⚠️ Pairs like and are always valid since one is the complement of the other ().
Example – Constraint violations
| Case | Situation | Violation |
|---|---|---|
| A | S0 → S1 on X, S0 → S2 on Y | (both may be true) and (no transition if both 0) |
| B | TCs and | Exclusive ✅, but ❌ |
| C | X/Z on one arc, Y/Z' (Z = 0) on another | → Z set to 1 and 0 at once ❌ |
| D | Moore output Z on a state + a transition action setting Z = 0 | Moore OC = 1, so no conflicting value is allowed on its arcs ❌ |
5. State Machine Table Format
| State | Code | Transition condition | Next state | Next code | Output actions (OCs) |
|---|---|---|---|---|---|
| Name | Code | (unused) | Unconditional next | Code | Moore or TCI outputs |
| TC₁ | Next₁ | Code₁ | TCD / TCOD outputs on TC₁ | ||
| … | … | … | … |
An asterisk * marks an action that depends on the transition condition.
Example – Table for the constraint-checking SMD
| State | Code | TC | Next | Code | Outputs |
|---|---|---|---|---|---|
| S0 | 00 | Y, Z | |||
| S1 | 01 | ||||
| S2 | 10 | ||||
| S1 | 01 | A/Y, B/Z | |||
| S2 | 10 | ||||
| S3 | 11 | ||||
| S2 | 10 | S3 | 11 | Y* | |
| S0 | 00 | Z* | |||
| S3 | 11 | S0 | 00 | (OC in )/Y* | |
| S1 | 01 | (OC in )/Y* |
⚠️ The S3 output conditions are products of B and C whose overbars were lost in the slide text — copy the exact complements from the diagram in your slides. Whatever they are, the two arcs are mutually exclusive ( vs ), so they can never conflict.
6. State Machine Design Procedure
- Define input and output variables and the meaning of their 0/1 values.
- Draw the SMD (or formulate the state machine table).
- Convert the SMD to a state machine table.
- Derive optimized next-state equations and output equations.
7. Example – Two-Floor Elevator Controller
⚠️ Simplified teaching example: no safety features and not all buttons.
Inputs
| Signal | Meaning of 1 |
|---|---|
| Call button (outside) pressed at floor 1 / 2 | |
| Go button (inside) pressed for floor 1 / 2 | |
| Elevator is at floor 1 / 2 | |
| Elevator is approaching floor 1 / 2 | |
| DO | Doors fully open |
| TO | Timer interval has ended |
| DC | Doors closed |
Outputs
| Signal | Meaning of 1 |
|---|---|
| Up / Down | Command elevator up / down |
| TS | Initialize and start timer |
| SD | Slow down (approaching target floor) |
| OD / CD | Open doors / close doors |
Operation
- Elevator parks, doors open, at the last floor served.
- A call/go button for the other floor starts the timer (TS).
- When TO = 1, doors close (CD); when DC = 1, Up or Down is activated.
- triggers SD (slow down); stops the motor and opens the doors.
States (one-hot)
Up (U), Down (Dn), and Hold split into three sub-states:
- Hd_A: open doors / wait for a request
- Hd_B: wait for timer
- Hd_C: close doors
State vector .
State Machine Diagram
Let (“doors open and a request for the other floor”).
stateDiagram-v2 [*] --> Hd_A Hd_A --> Hd_A : X' Hd_A --> Hd_B : X / TS Hd_B --> Hd_B : TO' Hd_B --> Hd_C : TO Hd_C --> Hd_C : DC'·(F1+F2) / CD Hd_C --> Dn : DC·F2 Hd_C --> U : DC·F1 Dn --> Dn : F1' Dn --> Hd_A : F1 U --> U : F2' U --> Hd_A : F2 note right of Hd_A : DO' / OD note right of Dn : Down, S1 / SD note right of U : Up, S2 / SD
⚠️ In the slide notation, keeps closing the doors (CD) until DC = 1.
State machine table
| State | Code | TC | Next | Code | Outputs |
|---|---|---|---|---|---|
| Hd_A | 00001 | /OD | |||
| Hd_A | 00001 | ||||
| Hd_B | 00010 | TS* | |||
| Hd_B | 00010 | Hd_B | 00010 | ||
| Hd_C | 00100 | ||||
| Hd_C | 00100 | Hd_C | 00100 | CD* | |
| Dn | 01000 | ||||
| U | 10000 | ||||
| Dn | 01000 | Down, /SD | |||
| Dn | 01000 | ||||
| Hd_A | 00001 | ||||
| U | 10000 | Up, /SD | |||
| U | 10000 | ||||
| Hd_A | 00001 |
Equations
With one-hot, = OR of all (source state · TC) entering that state.
Flip-flop inputs
Outputs
⚠️ The extracted slide text loses the overbars; e.g. has (arrived at floor 1) and — check each term against the SMD arcs.