Types Of Automata And It’s Application

11 min readJun 11, 2022

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.
An alphabet is a finite set of symbols.
A word is a finite string of symbols from a given alphabet.
Finally, a language is a set of words formed from a given alphabet

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:

Q: finite set of states
∑: finite set of the input symbol
q0: initial state
F: final state
δ: Transition function

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:

DFA(deterministic)
NFA(non-deterministic)

1.DFA

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

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
It is highly useful to design Lexical Analyzers
This automata is highly useful to design spell checkers.
For this automata is useful to design sequential circuit design (Transducer).
Another application of finite automata is programming simple agents to retort to inputs and produce actions in how. you’ll be able to write a full program, but a DFA is commonly enough to try to to the duty. DFAs are easier to reason about and easier to implement.

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:

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.

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
Growth of crystals especially patterns in snowflakes can be modeled by simple 2D CA
Excitable media in biology (predator-prey dynamics) and chemistry (Belousov-Zhabotinsky reaction) produce spiral patterns that can be seen in Greenberg-Hastings Models
Self-replication is seen in the Langton loop (which is a small component of a simplified version of the original von Neumann self-replicating machine)
Evolution (self-replication + mutation + selection) can be seen on the Evoloop model, a modified Langton loop
Fractal growth of biological organisms
Models of universal computation include rule 110 and the Game of Life
The Game of Life exhibits interesting patterns that can’t really be seen in the real world but they excite our imagination about what CA are capable of

Pushdown Automata

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;

` Q`: A finite set of states, like the states of a finite automation.
`∑`: A finite set of input alphabet/ symbols, also analogous to the corresponding component of a finite automaton.
`Γ`: A finite stack alphabet. This tuple, which has no finite-automaton analog, it the set of symbols that we are allowed to push onto the stack.
`δ`: The transaction function. As for a finite automation, δ governs the behavior of the automaton. Formally, δ takes as argument a triple δ(q, a, X), where;
q is a state in Q.
a is either an input symbol in ∑ or a = ε, the empty string, which is assumed not to be an input symbol.
X is a stack symbol, that is a member of Γ.

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.

q0: The initial state. The PDA is in this state before making any transitions.
z0: The stack start symbol. Initially, the PDA’s stack consists of one instance of this symbol, and nothing else.
F: The set of final states or accepting states.

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:

E→E+T|E−T|TE→E+T|E−T|TT→T∗F|T/F|FT→T∗F|T/F|FF→x|y|(E)|−F

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)

Linear Bound Automata

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).
The TM begins in the configuration (s, , 0).
The TM cannot replace with anything else, nor move the tape head left of .

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
For constructing syntactic parse trees for semantic analysis of the compiler

Turing Machine

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)

Note:
* 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

Building Chemical Computers using Turing Machine
Turing Test in Artificial Intelligence
Turing Machine Counting

❤ ❤ 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.