Automata Tutorial

What is Automata What is Automata theory Finite Automata Minimization of Finite Automata Conversion from NFA to DFA using Transition diagram Finite Automata with output Minimization of Finite Automata with output Conversion From Moore Machine to Mealy Machine Conversion From Mealy Machine to Moore Machine What do you mean by Regular Expression? Conversion from DFA to Regular expression Converting Finite Automata to Regular Conversion using Arden’s Theorem Pumping Lemma for Regular Languages Closure Properties of Regular Languages What do you mean by Context Free Grammar? Derivation Tree of Context Free Grammar What do you mean by Ambiguity in Context Free Grammar? Simplification in Context Free Grammar Chomsky Normal Form Greibach Normal Form Pumping Lemma for Context Free Languages Push Down Automata Non-deterministic Turing Machine Grammar in Automata How to Construct DFA NFA to Regular Expression Recursive Grammar in Automata Recursive Grammar in Automata Grammar in Automata | Types of Grammar How to Construct DFA? Expression Parsing

Finite Automata with Output
2020-12-09 05:30:32

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:

Moore Machine

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  

Transition table of Moore Machine

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.
Transition diagram of Moore Machine

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:

Mealy Machine

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.

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.

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  

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 table of Mealy Machine

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.
Transition diagram of a mealy machine