Finite Automata with Output

Finite Automata with Output

The Finite State machine is similar to Finite Automata, except that it has the additional capacity of producing output.

Finite State machine = Finite Automata + Output Capabilities

Types of Finite Automata that generates output are:

• Moore Machine
• Mealy Machine

The Mealy and Moore machine are commonly used to describe the behavior of sequential circuits, which include flip-flops, in which, the output of the circuits is related to both functions of the specific inputs and function of the previous state.

Moore Machine

The output of the Moore machine depends only on the present state. The general architecture of the Moore machine is:

In this, if the machine has N no of states, then it will require N-flip-flops, where M is the smallest number such that N<=2^M. If the input string is of length n, then the output string will be of length n+1.

Formal Notations of Moore Machine

The Moore machine contains 6 tuples or elements (Q, q0, ?, O, ?, ?).

Q: It is a collection of a finite set of states.

?: It is a collection of a finite set of input symbols.

?: By using the transition function, the states of the Moore machine move from one state to another state.

q₀: It is used for representing the initial state from which input is processed.

O: It is used for representing the output alphabet.

?:  It is an output function, where Q ? O  

Transition table of Moore Machine

In this transition table, we have input alphabet ? = {0, 1}and output alphabet O = {0, 1}. It takes input as {0, 1} and produces output in the form of {a, b}. Moore machine transition table also has the same input and output alphabet.

Transition diagram of Moore Machine

To create a transition diagram for a given problem, apply the following steps:

• First of all, determine the number of states needed from the given problem description.
• Represent each state with the help of a circle.
• From each state, draw an arrow causing event from the current state to the next state. If some particular input, the machine remains on the same state, then add this transition with the help of self-loop on the same state in the transition diagram.
• At last, write the value of the output in each state.

In Moore machine, initial state is indicated by an arrow. Each state contains two things, first is the name of the state, and the second is the output of the state.

Mealy Machine

In the Mealy machine, value of the output function depends on the current state q (t) and current input i (t). The architecture of mealy machine is given below:

In this, if the machine has N no of states, then it will require N-flip-flops, where M is the smallest number such that N<=2^M. In a mealy machine, if the input string of length n, then the output string will also be of length n.

Formal Notations of Mealy Machine

The mealy machine also contains 6 tuples or elements (Q, q0, ?, O, ?, ?)

Q: It is a collection of a finite set of states.

?: It is a collection of a finite set of input symbols.

?: By using the transition function, the states of the Mealy machine move from one state to another state.

q₀: It is used for representing the initial state from which input is processed.

O: It is used for representing the output alphabet.

?:  It is an output function where Q ? O  

Transition table of Mealy Machine

The output of the mealy machine depends on the current state and diagram. The transition table of the mealy machine is given below:

Transition diagram of a mealy machine

To create a transition diagram for a given problem, apply the following steps:

• First of all, determine the number of states needed for the given problem description.
• Represent each state with the help of a circle.
• From each state, draw an arrow causing event from the current state to the next state. If some particular input, the machine remains on the same state, then add this transition with the help of self-loop on the same state in the transition diagram.
• At last, write the output values along with the input values on the paths between the states.

In the mealy machine, each arc is labeled with two things:

• First is the input symbol
• The second is the output on the state.