BSCCS/2024/72127

MICAH MOSOMI

TOPIC: introductory state machine theory including mealy

machines and Moore machine, algorithm state machine chart

Introduction to State Machine Theory

State machines are computational models used to design digital logic systems,
control systems, and other sequential operations. They operate based on a finite
number of states and transitions between those states in response to inputs. There
are two primary types of finite state machines (FSMs): Mealy machines and
Moore machines.

Mealy Machine

Mealy machine combines the states and the inputs to produce outputs. This dual
dependency means that the machine's output can change in the middle of a state if
the input changes, providing a more immediate response to inputs compared to a
Moore machine.

Key Components:

1. Finite Set of States (S): These are the various conditions or modes in which
the machine can be.
2. Initial State (s₀): The state in which the machine starts its operation.
3. Finite Set of Input Symbols (Σ): The possible inputs the machine can
receive.
4. Finite Set of Output Symbols (Γ): The possible outputs the machine can
produce.
5. State Transition Function (δ: S × Σ → S): Defines the state transitions
based on the current state and input.
6. Output Function (λ: S × Σ → Γ): Defines the output based on the current
state and input.

Example Breakdown

Consider your example where the Mealy machine detects the sequence "01" in an
input stream:
State Transition Table
State Input Next State Output
s₀ 0 s₁ 0
s₀ 1 s₀ 0
s₁ 0 s₁ 0
s₁ 1 s₂ 1
s₂ 0 s₁ 0
s₂ 1 s₀ 0

 s₀: Initial state. If the input is 0, it moves to state s₁. If the input is 1, it
remains in s₀.
 s₁: If the input is 0, it stays in s₁. If the input is 1, it moves to state s₂ and
outputs 1.
 s₂: If the input is 0, it moves back to s₁. If the input is 1, it moves to s₀.

The detection of the "01" sequence results in an output of 1, and any other
sequence results in an output of 0.

Visualization

State Diagram

Here’s how the state diagram for this Mealy machine would look:

s₀ --(0)--> s₁ --(1)--> s₂
| | |
(1) (0) (0)
| | |
v v v
s₀ <-------- s₁ <--- --- s₀

 s₀: Initial state

 s₁: Transitioned to after receiving 0 from s₀.

 s₂: Transitioned to after receiving 1 from s₁.

Advantages of Mealy Machines

 Immediate Response: Outputs change immediately with inputs, providing

faster feedback.
 Efficient Use of States: Generally requires fewer states compared to Moore
machines for the same functionality.

Applications

 Pattern Recognition: Detecting specific sequences in input streams.

 Control Systems: Controlling processes based on continuous inputs.
 Communication Protocols: Managing the state of communication channels.

Detailed Explanation of Moore Machine

A Moore machine is a finite state machine where the outputs depend solely on the
current state, not on the inputs. This characteristic makes Moore machines simpler
in terms of output behavior compared to Mealy machines, as the output for each
state is fixed and doesn’t change with different inputs.

Key Components:

1. Finite Set of States (S): These represent the various conditions or modes in
which the machine can be.
2. Initial State (s₀): This is the starting state where the machine begins
operation.
3. Finite Set of Input Symbols (Σ): These are the possible inputs the machine
can receive.
4. Finite Set of Output Symbols (Γ): These are the possible outputs the
machine can produce.
5. State Transition Function (δ: S × Σ → S): Defines how the machine
transitions from one state to another based on the current state and the input
symbol.
 6. Output Function (λ: S → Γ): Defines the output for each state. Since it is
only dependent on the state, the output remains constant while the machine
is in a particular state.

Example Breakdown

Let’s explore a simple Moore machine that detects the sequence "01" and outputs 1
when in state s₂.

State Transition Table

State Input Next State Output
s₀ 0 s₁ 0
s₀ 1 s₀ 0
s₁ 0 s₁ 0
s₁ 1 s₂ 0
s₂ 0 s₁ 1
s₂ 1 s₀ 1

Explanation:

 s₀ (Initial State):
o If the input is 0, the machine moves to state s₁.
o If the input is 1, it remains in s₀.
o The output is 0.
 s₁:
o If the input is 0, the machine stays in s₁.
o If the input is 1, it transitions to state s₂.
o The output is 0.
 s₂:
o If the input is 0, the machine transitions to s₁.
o If the input is 1, it transitions to s₀.
o The output is 1.

State Diagram

The state diagram for this Moore machine would be:

s₀ -------(0)--> s₁ --(1)--> s₂
| | |
(1) (0) (0)
| | |
v v v
s₀ <-------- s₁ <------ s₀

Key Characteristics of Moore Machines:

1. State-Dependent Outputs: The output is determined solely by the current

state.
2. Stable Outputs: Outputs remain stable as long as the state doesn’t change.
3. Simpler Output Logic: Since outputs don’t directly depend on inputs, the
output logic tends to be simpler.

Advantages of Moore Machines:

 Predictable Outputs: Outputs are easier to predict and verify, as they are
state-dependent.
 Simplified Design: The separation of state transitions and output logic can
simplify the design process.

Applications:

 Sequential Logic Circuits: Used in digital circuits where stable outputs are
required.
 Controllers: Widely used in control systems where consistent outputs are
crucial, such as traffic light controllers.
 Protocol Design: Useful in communication protocols where the system must
maintain consistent states.

Comparison with Mealy Machine:

 Mealy Machine: Outputs depend on both current state and input. This can
lead to faster response times.
 Moore Machine: Outputs depend only on the current state, resulting in
stable and predictable outputs.
Algorithm State Machine (ASM) Chart

An ASM chart is a powerful tool used in digital design and system control to
represent the behavior of sequential logic circuits. It combines elements of state
diagrams and flowcharts to create a more comprehensive and visually intuitive
representation of operations. ASM charts are particularly valuable for designing
and understanding the flow of operations within complex digital systems.

Components of an ASM Chart

1. State Boxes:
o Represent states and the corresponding outputs.
o Each state box contains the state name and the output that is active
when the system is in that state.
2. Decision Boxes:
o Represent conditions or decisions based on inputs.
o These boxes direct the flow to different branches depending on the
evaluation of a condition.
3. Conditional Outputs:
o Outputs that depend on both states and inputs.
o These are typically represented within the paths connecting decision
boxes to state boxes.

Example ASM Chart

Let's illustrate an ASM chart for a simple sequence detector that detects the
sequence "101" in an input stream. This example will help you understand how an
ASM chart combines state and decision logic.

Detailed Example: Sequence Detector for "101"

1. State Box (s₀: Initial State, Output 0)

o Represents the initial state of the machine where no part of the "101"
sequence has been detected.
o Output is 0 since the target sequence has not yet been identified.
2. Decision Box (Input Evaluation)
o Condition: If the input is 1, transition to state s₁.
o Else: Remain in state s₀.
o This evaluates the input and directs the machine to the next
appropriate state based on the input value.
3. State Box (s₁: Intermediate State, Output 0)
 o Represents the state where the first 1 of the "101" sequence has been
detected.
o Output remains 0 since the full sequence has not been completed yet.
4. Decision Box (Input Evaluation)
o Condition: If the input is 0, transition to state s₂.
o Else: Transition back to state s₀ (if the input is 1, it means the
sequence is incorrect for "101").
5. State Box (s₂: Intermediate State, Output 0)
o Represents the state where the "10" part of the sequence has been
detected.
o Output remains 0.
6. Decision Box (Input Evaluation)
o Condition: If the input is 1, transition to state s₃.
o Else: Transition back to state s₀.
7. State Box (s₃: Sequence Detected, Output 1)
o Represents the state where the full "101" sequence has been detected.
o Output is 1 indicating successful detection of the sequence.

Visual Representation

To visualize the transitions, let's depict them in a more narrative form:

 State s₀:
o Initially, the system is in state s₀ with an output of 0.
o If the input is 1, the system transitions to state s₁. Otherwise, it
remains in s₀.
 State s₁:
o In s₁, if the input is 0, the system transitions to state s₂. If the input is
1, it goes back to s₀.
 State s₂:
o In s₂, if the input is 1, the system moves to state s₃. If the input is 0, it
goes back to s₀.
 State s₃:
o In s₃, the output is 1 to indicate the "101" sequence detection.

Advantages of Using ASM Charts

1. Clarity: Provides a clear and structured visual representation of the state

transitions and conditions.
 2. Combination of State and Logic: Combines the features of flowcharts
(decision-making) and state diagrams (state transitions), making it easier to
design and understand complex systems.
3. Documentation: Acts as excellent documentation for explaining and
validating the logic of digital systems.
4. Verification: Simplifies the verification and debugging process of
sequential circuits.

Comparing Mealy and Moore Machines

Mealy Machine:

 Outputs depend on the current state and input.

 Faster response times as outputs can change immediately with inputs.
 Complex output logic due to dependence on inputs.

Moore Machine:

 Outputs depend only on the current state.

 Stable outputs since they only change with state transitions.
 Simpler output logic because outputs are independent of inputs.