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:
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.
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<=2M. 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.
q0: 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
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.
To create a transition diagram for a given problem, apply the following steps:
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.
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<=2M. In a mealy machine, if the input string of length n, then the output string will also be of length n.
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.
q0: 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
The output of the mealy machine depends on the current state and diagram. The transition table of the mealy machine is given below:
To create a transition diagram for a given problem, apply the following steps:
In the mealy machine, each arc is labeled with two things:
