1. Finite State Machines

Definition – Finite State Machine (FSM)

An FSM consists of three sets and two functions:

ElementMeaning
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

TermDefinition
Input conditionBoolean 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 transitionArc with no TC (or TC = 1)
Conditional transitionArc with one or more TCs; taken if any is 1

Definitions – Output action types

TypeAttached toOccurs when
Moore (unconditional)StateAlways while in the state
TCI Mealy (transition-condition-independent)State, written OC/actionOC = 1
TCD Mealy (transition-condition-dependent)Arc’s TCThat TC = 1
TCOD Mealy (transition-and-output-condition-dependent)Arc’s TC, written OC/actionTC = 1 and OC = 1

Moore and TCI actions attached to a state apply on all transitions leaving it.

Output action notation

  • Single variable: writing Z means 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.

StyleNotation in S0Result
MooreY, Z on S0Y = Z = 1 whenever in S0
TCIA/Y, B/Z on S0Y = A, Z = B in S0
TCDA·B/Y and (A'+B')/Z on arcsY = 1 on the S1 arc, Z = 1 on the S2 arc
TCODC/Y on each arcY = 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 )

  1. Mutually exclusive: for every pair of TCs to distinct next states, .
  2. All-inclusive: (some transition always defined).

Output-condition constraints (for each state )

  1. For actions giving the same output variable different values, their OCs must be mutually exclusive: .
  2. 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.

StateTransitions
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

CaseSituationViolation
AS0 → S1 on X, S0 → S2 on Y (both may be true) and (no transition if both 0)
BTCs and Exclusive ✅, but ❌
CX/Z on one arc, Y/Z' (Z = 0) on another → Z set to 1 and 0 at once ❌
DMoore output Z on a state + a transition action setting Z = 0Moore OC = 1, so no conflicting value is allowed on its arcs ❌

5. State Machine Table Format

StateCodeTransition conditionNext stateNext codeOutput actions (OCs)
NameCode(unused)Unconditional nextCodeMoore 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

StateCodeTCNextCodeOutputs
S000Y, Z
S101
S210
S101A/Y, B/Z
S210
S311
S210S311Y*
S000Z*
S311S000(OC in )/Y*
S101(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

  1. Define input and output variables and the meaning of their 0/1 values.
  2. Draw the SMD (or formulate the state machine table).
  3. Convert the SMD to a state machine table.
  4. 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

SignalMeaning 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
DODoors fully open
TOTimer interval has ended
DCDoors closed

Outputs

SignalMeaning of 1
Up / DownCommand elevator up / down
TSInitialize and start timer
SDSlow down (approaching target floor)
OD / CDOpen doors / close doors

Operation

  1. Elevator parks, doors open, at the last floor served.
  2. A call/go button for the other floor starts the timer (TS).
  3. When TO = 1, doors close (CD); when DC = 1, Up or Down is activated.
  4. 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

StateCodeTCNextCodeOutputs
Hd_A00001/OD
Hd_A00001
Hd_B00010TS*
Hd_B00010Hd_B00010
Hd_C00100
Hd_C00100Hd_C00100CD*
Dn01000
U10000
Dn01000Down, /SD
Dn01000
Hd_A00001
U10000Up, /SD
U10000
Hd_A00001

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.