Types Of Automata And It’s Application

Image by Pinterest

Automata theory is the basis for the theory of formal languages. It is the study of abstract machines and the computation problems that can be solved using these machines. The abstract machine is called the automata.The main motivation behind developing the automata theory was to develop methods to describe and analyse the dynamic behaviour of discrete systems. A Proper treatment of formal language theory begins with some basic definitions:

  • A symbol is simply a character, an abstraction that is meaningless by itself.

Types of Automata and its applications

Finite Automata

Finite automata are use to recognize patterns.An automaton with a finite number of states is called a Finite automaton. It takes the string of symbol as input and changes its state accordingly. When the desiring symbol is search, then the transition occurs. At the time of transition, the automata can either move to the next state or stay in the same state. Finite automata have two states, Accept state or Reject state. When the input string is processing successfully, and the automata reached its final state, then it will accept.

Finite Automata Model:

A finite automaton is a collection and machine of 5-tuple (Q, ∑, δ, q0, F), where:

  1. Q: finite set of states

Note: Input tape is a linear tape having some number of cells. Each input symbol is place in each cell.

Finite control: The finite control decides the next state on receiving particular input from input tape. The tape reader reads the cells one to one from left to right, and at a time only one input symbol is read.

Types of Automata:

There are two types of finite automata:

  1. DFA(deterministic)


Image by Gate Vidyalaya

DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. In the DFA, the machine goes to one state only for a particular input character. DFA does not accept the null move.

2. NFA

Image by Gate Vidyalaya

NFA stands for non-deterministic automata. It is used to transmit any number of states for a particular input. It can accept the null move.

Some important points about DFA and NFA:

* Every DFA is NFA, but NFA is not DFA.
* There can be multiple final states in both NFA and DFA.
* DFA is used in Lexical Analysis in Compiler.
* NFA is more of a theoretical concept.

Applications of Finite Automata (FA):

  • Software for designing and checking the behavior of digital circuits

Cellular Automata

Cellular automata is a deterministic rewriting dynamic systems that evolves in discrete time and discrete space, the latter usually a grid. It consists of a grid of cells that are locally but synchronously updated across the grid according to a global time scale and a global recursive rule governing the evolution of the state of each cell as a function of the state of neighboring cells.

While the model of cellular automata is of the same computational power than other Turing universal models and, therefore, fundamentally equivalent as they can emulate each other.

Typically, a CA neighborhood is defined as an automaton and its immediate neighbors. The two most common neighborhood templates used for a two-dimensional lattice are:

Figure: Two most common 2-D CA neighborhood templates.

Since the automata are using state configurations of a given template as their input source, the set of all possible configurations for a given template is isomorphic to the set of input symbols that the automata need recognize.

To simplify construction of CA systems, the following conventions are universally employed:

  1. All FA are defined to use the same set of state symbols

2. All FA use the same neighborhood template

3. As a consequence of 1 and 2, all FA will be recognizing the exact same set of state configurations. Thus, it its natural to define all automata to use the same input symbol alphabet

Computation in CA

The Game of Life is a concrete example that CA can support universal computation. However, that CA can be functionally universal has been known since its invention by Ulam and von Neumann in the 1940s. In his existence proof of such self-reproducing machines, von Neumann demonstrated the existence of a universal computer using a two-dimensional, 29-state cellular automaton with the 5-neighborhood template. From this proof stemmed subsequent proofs of automata with much fewer states supporting universal computation.

Gif by Wolfram Mathworld

Applications of Cellular Automata (CA)

Let us just list some examples of physical phenomena and CA that exhibit similar behavior:

  • Patterns on sea shells Cymbiola innexa are similar to patterns generated by rule 30 1D CA

Pushdown Automata

Gif by Dev Community

The formal notation for a pushdown automata (PDA) involves seven tuples. We write the specification of a PDA ‘M’ as follows;

M = (Q, ∑, Γ, δ, q0 , z0, F)

These tuples have the following meaning;

  1. ` Q`: A finite set of states, like the states of a finite automation.

Basically the complete transaction function of pushdown automata is as;

δ: (Q x (Σ ∪{ε}) x X) → (p, γ)

Here the output of δ is a finite set of pair (p, γ), where p is the new state, and γ is the string of stack symbols that replaces X at the top of the stack. For instance, if γ = ε, then the stack is popped, if γ = X, then the stack is unchanged, and if γ = YZ, then X is replaced by Z and Y is pushed onto the stack.

  1. q0: The initial state. The PDA is in this state before making any transitions.

Pushdown Automata has a Stack mechanism to accept languages which aren’t possible in a Finite Automata. The problem comes when before a Push operation we need to check for Overflow Condition, or before a Pop Operation we check for the Underflow Condition.

We solve this problem by assuming that the Stack is infinite, while the empty condition is overcome by pre introducing an element Z0 into the stack before working on the string.

Applications of Pushdown Automata

  • Whenever your smartphone calculator calculates an arithmetic expression, it uses an implementation of the push down automata to evaluate it. It verifies that the parentheses are balanced. In the absence of parentheses, it makes sure that the multiplication operator has more precedence than the addition or subtraction operator. All of it can be summarized in three lines of grammar:
  • Online Transaction Processing system

In this work an attempt is made to model the online transaction processing system of a banking organization with timed automata. In Figure the organization of the bank is depicted. It consists of multiple branches with multiple tellers at each branch.

  • Tower Of Hanoi (Recursive Solution)
Image by Viblo

Linear Bound Automata

Image by Youth4work

A Turing machine that uses only the tape space occupied by the input is called a linear-bounded automaton (LBA).An LBA differs from a Turing machine in that while the tape is initially considered to have unbounded length, only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head; hence the name linear bounded automaton.

Linear bounded automata is a non-deterministic Turing machine

M = (Q , T , E , q0 , ML , MR , S , F), where,  
Q -> A finite set of transition states
T -> Tape alphabet
E -> Input alphabet
q0 -> Initial state
ML -> Left bound of tape
MR -> Right bound of tape
S -> Transition Function
F -> A finite set of final states
  • There are two special tape symbols (the left end marker and right end marker).

An equivalent definition of an Linear Bound Automata(LBA) is that it uses only k times the amount of space occupied by the input string, where k is a constant fixed for the particular machine. Possible to simulate k tape cells with a single tape cell, by increasing the size of the tape alphabet.

Examples: {a^n | n is a perfect square }

Used as a model for actual computers rather than models for the computational process.

Applications of Linear Bound Automata

  • Genetic Programming

Turing Machine

Image by Futurelearn

Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer. It consists of an infinitely long tape, which has been divided up into cells. Each cell can contain either a 1, a 0, or an empty space. Above one cell of the tape is a head, which can either move left or right, and can read the symbols written in the cells. The head is also capable of erasing symbols and writing new symbols into the cells.

The Turing machine is not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.

A Turing Machine can be formally described as :

7-tuple (Q, X, ∑, δ, q0, B, F) where −
* Q is a finite set of states
* X is the tape alphabet
* ∑ is the input alphabet
* δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
* q0 is the initial state
* B is the blank symbol
* F is the set of final states

Time and Space Complexity of a Turing Machine

For a Turing machine, the time complexity refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written.

Time complexity all reasonable functions −

T(n) = O(n log n)

TM’s space complexity −

S(n) = O(n)


* In non-deterministic Turing machine, there can be more than one possible move for a given state and tape symbol, but non-deterministic TM does not add any power.

* Every non-deterministic TM can be converted into deterministic TM.

* In multi-tape Turing machine, there can be more than one tape and corresponding head pointers, but it does not add any power to Turing machine.

* Every multi-tape TM can be converted into single tape TM.

Applications of Turing Machine

  • Read/Write Head
Image by GeeksforGeeks
  • Building Chemical Computers using Turing Machine

❤ ❤ Thanks for reading this post❤❤

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or you find anything incorrect? Let us know in the comments. Thank you!

Clap 👏 If this article helps you.



Vishwakarma institute of techonology ,fourth year student

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store