Automata theory

Automata Theory is an interesting, exciting, theoretical branch of computer science that deals with designing abstract self-propelled computing devices that follow a predetermined sequence of operations automatically. The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means “self-acting”.

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₁, x,₂, x₃… 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₁, y₂, y₃ … 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 5-tuple (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₀ = {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

 

• Non-deterministic 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 Non-deterministic Automaton. As it has finite number of states, the machine is called Non-deterministic Finite Machine or Non-deterministic Finite Automaton.

Formal Definition of NFA:

An NFA | NDFA can be represented by a 5-tuple (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₀ = {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 context-free 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 7-tuple (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 one-dimensional 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 Tech-Blogs for more informative technology related blogs https://msatechnosoft.in/blog/category/tech-blogs/