Automata theory
Automata Theory is an interesting, exciting, theoretical branch of computer science that deals with designing abstract selfpropelled computing devices that follow a predetermined sequence of operations automatically. The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means “selfacting”.
Automata Theory established its roots during the 20th Century, as mathematicians began machines which imitated certain features of man, completing calculations more quickly and reliably. Automata theory is combinational study of theoretical computer science and discrete mathematics.
Automata theory allows computer scientists to understand how machines compute functions and solve problems. It also help them to understand what it means for a function to be defined as computable or for a question to be described as decidable.
The main objective of automata theory is to develop methods for computer scientists that can describe and analyse the dynamic behaviour of discrete systems. Signals are sampled periodically in such systems. Behaviour of the system is determined from storage and combinational elements using which it is created. Characteristics of such machines include:
 Inputs: sequences of symbols selected from a finite set / of input signals. Where I is the set {x_{1}, x,_{2}, x_{3}… x_{k}} where k is the number of inputs.
 Outputs: sequences of symbols selected from a finite set Z. where Z is the set {y_{1}, y_{2}, y_{3} … y_{m}} where m is the number of outputs.
 States: finite set Q, whose definition depends on the type of automaton.
Finite Automata
An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine.
Formal definition of Finite Automata
An automaton can be represented by a 5tuple (Q, ∑, δ, q0, F), where
 Q is a finite set of states.
 ∑ is a finite set of symbols, called the alphabet of the automaton.
 δ is the transition function.
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).
Finite Automaton can be classified into two types −

Deterministic Finite Automaton (DFA)
For each input symbol the state to which the machine will move can be determined. It has a finite number of states hence called Determined Finite Automata or DFA.
Formal definition of DFA
DFA consists of 5 tuples {Q, ∑, q, F, δ}.
 Q set of all states.
 ∑ set of input symbols. ( Symbols which machine takes as input )
 q Initial state. ( Starting state of a machine )
 F set of final state.
 δ Transition Function, defined as δ : Q X ∑ –> Q.
Example of DFA
Let us assume a DFA Q = {a, b, c}, ∑ = {0, 1}, q_{0} = {a}, F = {c}, and
Transition function δ as follow
Present State 
Next State for Input 0  Next State for Input 1 
a 
a 
b 
b 
c 
a 
c  b 
c 
Then, we can represent it graphically as

Nondeterministic Finite Automaton (NDFA / NFA)
In NDFA, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined. Hence, it is called Nondeterministic Automaton. As it has finite number of states, the machine is called Nondeterministic Finite Machine or Nondeterministic Finite Automaton.
Formal Definition of NFA:
An NFA  NDFA can be represented by a 5tuple (Q, ∑, δ, q0, F) where
 Q is a finite set of states.
 ∑ is a finite set of symbols called the alphabets.
 δ is the transition function where δ: Q × ∑ → 2Q (Here the power set of Q (2Q) represent any combination of Q states)
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).
An NFA is represented by digraphs called state diagram.
Example of NFA:
Let us assume an NFA Q = {a, b, c}, ∑ = {0, 1}, q_{0} = {a}, F = {c}
The transition function δ as below
Present State  Next State for Input 0  Next State for Input 1 
a 
a, b 
b 
b 
c 
a, c 
c 
b, c 
c 
Then, we can represent it graphically as
Pushdown Automata
A pushdown automaton is used to implement a contextfree grammar in same way we design DFA for a regular grammar. DFA can remember a finite amount of information while PDA can remember an infinite amount of information.
A pushdown automaton has three components − an input tape, a control unit, and a stack with infinite size. The stack head read top element of the stack.
A stack does two operations – Push (to add an element at stack top), Pop (to remove the top element of stack).
A PDA read the top of the stack in every transition.
Formal Definition of PDA
A PDA can be formally described as a 7tuple (Q, ∑, S, δ, q0, I, F)
 Q is the finite number of states
 ∑ is input alphabet
 S is stack symbols
 δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*
 q0 is the initial state (q0 ∈ Q)
 I is the initial stack top symbol (I ∈ S)
 F is a set of accepting states (F ∈ Q)
Turing Machine
Turing Machine was invented by Alan Turing in 1936. It is an accepting device that accept recursively enumerable set of languages generated by type 0 grammars.
The Turing machine can be imagined as a finite automaton or control unit equipped with an infinite storage. Its “memory” consists of an infinite number of onedimensional array of cells. Turing machine is essentially an abstract model of modern computer execution and storage. It was developed in order to provide a precise mathematical definition of an algorithm or mechanical procedure.
Formal definition of Turing Machine
A Turing machine is formally defined by the set [Q, Σ, Γ, δ, q0, B, F] where
 Q finite set of states, of which one state q0 is the initial state
 Σ a subset of Γ not including B, is the set of input symbols
 Γ finite set of allowable tape symbols
 δ the next move function , a mapping function from Q x Γ to Q x Γ x {L,R}, where L and R denote the directions left and right respectively
 q0 in set Q as the start state
 B a symbol of Γ, as the blank
 F ⊆ Q the set of final states
Turing machine is capable of changing symbols on its tape and simulating computer execution and storage. That is why Turing Machine has the power to model all computations that can be calculated today through modern computers.
Must share your views as comment below. Don’t forget to checkout TechBlogs for more informative technology related blogs https://msatechnosoft.in/blog/category/techblogs/
3 Comments
Wendy Bennetts · May 25, 2018 at 10:59 AM
Thanks for sharing this post. This is first article that make me understand what automata actually is. Keep sharing.
MSA Technosoft · May 31, 2018 at 1:59 PM
Thank you for your appreciation! We’d love to see you again!
Roman Royal · August 31, 2018 at 11:35 PM
You have an amazing collection of articles. I have gone through some of them and i really appreciate your work. You have the art of writing well. I have already bookmarked it for upcoming posts. Thanks.