Finite Automata with Output
COS2601 - Theoretical Computer Science II · Automata Theory
Finite Automata with Output
Introduction to Moore Machines
A Moore machine is a type of finite automaton that produces output based on its states. It consists of five components:
- A finite set of states, where one state is designated as the start state.
- An alphabet of input symbols.
- An alphabet of output symbols.
- A transition table that defines state transitions based on input symbols.
- An output table that specifies the output character for each state.
The key characteristic of a Moore machine is that the output depends only on the current state, not on the input symbol being processed. This means that every time the machine enters a state, it produces a specific output.
Structure of a Moore Machine
Let us define a Moore machine formally:
Definition: A Moore machine is defined as a 5-tuple (Q, I, O, δ, λ), where:
- Q is a finite set of states.
- I is a finite input alphabet.
- O is a finite output alphabet.
- δ: Q × I → Q is the transition function.
- λ: Q → O is the output function.
Notice that the output alphabet O is distinct from the input alphabet I. This allows for flexibility in the types of outputs produced based on the states.
Example of a Moore Machine
Consider a simple Moore machine defined as follows:
- Input alphabet: I = {a, b}
- Output alphabet: O = {0, 1}
- States: Q = {q0, q1, q2, q3}, where q0 is the start state.
The transition table for this machine is:
| Current State | Input | Next State | Output |
|---|---|---|---|
| q0 | a | q1 | 1 |
| q0 | b | q3 | 0 |
| q1 | a | q2 | 0 |
| q1 | b | q3 | 1 |
| q2 | a | q1 | 0 |
| q2 | b | q3 | 1 |
| q3 | a | q3 | 0 |
| q3 | b | q2 | 1 |
This machine can be represented pictorially. Each state is depicted as a circle, with the output indicated inside the circle:
Operation of the Moore Machine
Let us trace the operation of the above Moore machine with the input string abab. We start in the initial state q0:
- At q0, the first input is a, moving to q1 and outputting 1.
- At q1, the next input is b, moving to q3 and outputting 1.
- At q3, the next input is a, remaining in q3 and outputting 0.
- At q3, the final input is b, moving to q2 and outputting 1.
The output sequence for the input string abab is 1101.
Watch out: Remember that the output is determined by the state, not the input. Each state has a fixed output regardless of the input that caused the transition.
Moore Machines and Language Recognition
Moore machines do not define a language in the traditional sense because they do not have final states. Instead, they produce an output string for every possible input string. However, we can derive useful information about the input strings based on the output produced.
Introduction to Mealy Machines
A Mealy machine is similar to a Moore machine but differs in how the output is generated. In a Mealy machine, the output is produced based on the transitions between states rather than the states themselves. This means that the output can change depending on the input symbol being processed.
Structure of a Mealy Machine
Let us define a Mealy machine formally:
Definition: A Mealy machine is defined as a 6-tuple (Q, I, O, δ, λ), where:
- Q is a finite set of states.
- I is a finite input alphabet.
- O is a finite output alphabet.
- δ: Q × I → Q is the transition function.
- λ: Q × I → O is the output function.
Example of a Mealy Machine
Consider a simple Mealy machine defined as follows:
- Input alphabet: I = {a, b}
- Output alphabet: O = {0, 1}
- States: Q = {q0, q1, q2, q3}, where q0 is the start state.
The pictorial representation of this machine is:
In this machine, the edges between states are labeled with both the input and the output. For example, an edge labeled a/0 means that when the input is a, the output is 0.
Operation of the Mealy Machine
Let us trace the operation of the Mealy machine with the input string aaabb. We start in the initial state q0:
- At q0, the first input is a, moving to q1 and outputting 0.
- At q1, the next input is a, moving to q3 and outputting 1.
- At q3, the next input is a, remaining in q3 and outputting 1.
- At q3, the next input is b, moving to q0 and outputting 1.
- At q0, the final input is b, moving to q3 and outputting 0.
The output sequence for the input string aaabb is 01110.
Watch out: In a Mealy machine, the output is produced during the transitions, so the output string will often have the same number of characters as the input string.
Comparing Moore and Mealy Machines
Both Moore and Mealy machines are equivalent in terms of the types of languages they can recognize. However, they differ in how and when they produce output. Moore machines produce output based solely on the current state, while Mealy machines produce output based on the transitions between states.
Summary
- A Moore machine outputs based on its states, while a Mealy machine outputs based on transitions.
- Moore machines have a fixed output for each state, while Mealy machines can have different outputs for the same state depending on the input.
- Both types of machines are used in computer science to model systems and processes.
Check your understanding
- What are the five components of a Moore machine?
- How does the output of a Mealy machine differ from that of a Moore machine?
- Trace the operation of a Moore machine with the input string abab.
- What is the significance of the transition table in both Moore and Mealy machines?