Pushdown Automata Vs Turing Machine
Theory of Automata is basically that theorotical branch of computer science and mathematics which is a study of abstract machines and the computation problems that can be solved using these machines.
The extract of Theory of computation is to help in developing of mathematical and logical model that runs efficiently
Here, the abstract machine is known as Automata. Basic Computation performed by an Automata is defined by these features which are set of input symbols, The configuration states, and the Output.
Introduction to Finite Automata(FA) and Regular Grammar(RE)
Before moving ahead and talking on Pushdown Automata let’s talk on some basic terms of Automata which are RE(Regular expression or Grammar) FA (Finite Automata), DFA (Deterministic finite automata), NFA (Non- Deterministic Finite Automata) and CFG (Context Free Grammar).
Finite Automata (FA) it is the simplest machine to recognize patterns and to solve the regular problems, we can also call it a finite state machine that have 5 tuples namely
- Q: Finite set of states,
- Σ: set of input symbols
- q: Initial state,
- F: set of final state
- δ: mapping function or transition function.
Finite Automata is a machine which is used to solve problems in Regular Expression(RE) , or we can say it is a Type 3 Grammar which is the most basic language. These are most restricted type of languages and are accepted by Finite automata
Now here the Finite Automata is categorized into two parts (DFA: deterministic Finite Automata and Non-deterministic Finite Automata)
DFA(Deterministic Finite Automata):If one can determine the state to which the machine would move for each input symbol, then this kind of Automata is known as the Deterministic Automata. As here a finite number of states are present hence called Deterministic Finite Automata abbreviated as DFA.
NFA (non-deterministic finite automata), a finite automata is called NFA when there are many paths for single input from current state to final state. Alo NFA is Easier to construct as compared to DFA because it allows Dead state configuration, also it consists of Null state transition which DFA doesn’t allow.
Context free Grammar
CFG: A formal grammar used to generate all possible patterns of a string in each formal language is what we call Context Free Grammar or CFG. Context free grammar is defined from 4 tuples which are (V: variable set, T: terminal set, P: Production rule, S: Start Symbol).
CFG is a Type 2 Language. We can say that CFG and PDA are equivalent in power, CFG generates context free language which is then recognized by PDA (Pushdown Automata) and then solves the given problem. It is also said that if PDA recognizes a language then it has to be a context free language.
What is Pushdown Automata ?
Before moving ahead and talking on Pushdown Automata let’s talk on some basic terms of Automata which are DFA(Deterministic finite automata) and CFG(Context Free Grammar).
If one can determine the state to which the machine would move for each onput symbol then this kind of Automata is known as the Deterministic Automata. As here finite number of states are present hence called Deterministic Finite Automata abbreaviated as DFA.
A formal grammer used to generate all possible patterns of a string in a given formal language is what we call Context Free Grammer or CFG.
Now as we know about DFA and CFG in brief, now let’s talk on Pushdown Automata. So, Pushdown Automata(PDA) is a method to implement CFG in the same way as we implement DFA for regular grammer. The difference here is that DFA can remember only finite amount of data where as Pushdown Automata can remember an infinite amount of data. Hence, in simple words
Pushdown Automata = “Finite state machine” + “a stack”
Structure of Pushdown Automata
Since, as we have discussed on Pushdown Automata in brief, let’s now discuss the structure. The Pushdown Automata consists of 3 basic components that are :
Input Tape
Control Unit
Stack with infinte size.
The stack has got to do 2 basic operations that is
Push : Adding a new symbol at the top
Pop : Reading and removing the top symbol.
A PDA is formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) :
Q signifies the finite number of states
∑ signifies Input alphabet
S signifies Stack symbols
δ signifies the transition function: Q × (∑ ∪ {ε}) × S × Q × S*
q0 signifies the initial state (q0 ∈ Q)
I signifies the initial stack top symbol (I ∈ S)
F signifies a set of accepting states (F ∈ Q)
Associated Terminologies for PDA Instantaneous Description:
A triplet (q, w, s) represents the instantaneous description (ID) of a PDA.
The state is q.
w denotes input that has not yet been consumed.
The contents of the stack are denoted by the letter s.
PDA transition from one state to another
This indicates that if an input string ‘a’ is encountered at state q1 and the top symbol of the stack is ‘b,’ we pop ‘b ‘, push ‘c’ to the top of the stack, and go to state q2.
Unrestricted Grammar
Unrestricted Grammar is a type of Formal Grammar, where the finite set of non- terminal symbols, is a finite set of terminal symbols and are disjoint, is a finite set of production rules.
Unrestricted grammar is 4 tuples :
G = (N,Σ,P,S)
Where,
N signifies a finite set of non-terminal symbols
∑ signifies set of terminal symbols or alphabets of the language being described, where N union ∑ =δ
P signifies finite set of “rules” or “production”
S signifies a start variable
It is also Known as the Type 0 grammar; these languages are also known as the Recursive enumerable language and these languages contain all the other languages under it. So basically, this type 0, recursive Enumerable language is recognized by the Turing machine. When the Grammar becomes hard to understand by LBA , PDA and FA then the Turing machine definitely recognises it
What is a Turing Machine ?
Invented in 1936 by Alan Turing, this is a device which accepts Recursive Enumerable Language generated by type 0 grammar.
Let’s understand this definition in a better way by discussing on the working of Turing Machine.
So, Turing Machine is basically a mathematical model. It consists of an infinite length tape which is divided into cells which has one head on which we take the input. There is a state register present which stores the state of the Turing machine. Following the reading of an input symbol, it is replaced with a different symbol, its internal state is changed, and it advances from one cell to the right or left. At the end if the TM reaches the final state it is accepted else rejected.
A Turing Machine is described formally as a 7-tuple (Q, X, ∑, δ, q0, B, F) where :
Q signifies a finite set of states
X signifies the tape alphabet
∑ signifies the input alphabet
δ signifies a transition function; δ : Q × X → Q × X × {Left shift, Right shift}.
q0 signifies the initial state
B signifies the blank symbol
F signifies the set of final states
Deterministic and Non-deterministic Turing Machine
Deterministic Turing machine is true to the name to the fact that every computation can be viewed as a sequence of linear order (finite or infinite ). The element which is first has the initial state and every configuration C0 is followed directly by configuration C in the pattern. If the turing machine can as a sequence of a valid move of the machine, change C to C0.
Nondeterministic turing machines are not restricted to ordered computation such as deterministic. At every movement a nondeterministic turing machine can allow various moves or choose in between a number of possibilities). Hence in many possible ways computation can be “branched”.The best described computation which is the resulting computation , as a rooted tree of configuration. Each and every deterministic computation comparable to a particular sequence of choice is said to be a computation path.
Comparison between Pushdown Automata and Turing Machine
- Pushdown Automata is not Deterministic where as Turing Machine is Deterministic in nature.
- A Pushdown Automata can access only top of the stack as it works on the Last In First Out(LIFO) concept where as the Turing Machine can access any position on the infinite tape.
- As the infinite tape cannot be simulated with a single stack, hence Pushdown Automata becomes less computationally powerful and also there are algorithms that can be programmed with a Turing Machine that cannot be programmed with a Pushdown Automata.
- Pushdown Automata is used for designing the parsing phase of a compiler in Syntax Analysis. Turing Machine is used for implementation in Neural Networks.
- The popular Tower of Hanoi Problem is solved using the Pushdown Automata. Turing Machine has got applications in the field of Artifical Intelligence and Robotics.
- All the applications in which is stack is involved are done using Pushdown Automata and it is also helpful in solving arithmetic expressions. Turing Machine is very helpful in understanding complexity theory.
Application of PDA in Tower of Hanoi
The Tower of Hanoi is a renowned mathematics puzzle known for its recursive programming. It is made up of three poles and a variety of discs of varying sizes that may be slid onto any of the poles. The problem begins with the discs stacked neatly in ascending order of size in one pole, with the smallest at the top, forming a conical shape. The goal of the problem is to shift all of the discs from one pole to another using a third pole.
The rules of the problem are as follows:
You can’t put a larger disc on top of a smaller disc
At any given moment, only one disc may be transferred.
The puzzle may be played with any number of discs, although most toy versions contain 7 to 9 of them. A Tower of Hanoi problem requires a minimum of 2n-1, where n is the number of discs. This is the exact nth Merenesse Number. This puzzle is supposed to have originated in India, where there is a temple with three pillars and 64 rings. It is stated that when the puzzle is completed, the world will come to an end. According to the algorithms, the minimal number of movements is 2n-1, therefore 2⁶⁴-1, moves are required. That’s a lot of time, so don’t worry.
Application of Turing Machine in Neural Networks
A Neural Turing machine (NTM) is a Turing machine-modeling recurrent neural network. Alex Graves et al. published the method in 2014. NTMs combine neural networks’ fuzzy pattern matching skills with the computational capability of programmable computers. An NTM has a neural network controller that is linked to external memory resources with which it interacts via attentional mechanisms. Because the memory interactions are differentiable from end to end, they can be optimised via gradient descent. From examples alone, an NTM with a long short-term memory (LSTM) network controller may infer basic algorithms such as copying, sorting, and associative recall.
The authors of the original NTM article did not make their source code available. The first stable open-source implementation was presented with a best-paper prize at the 27th International Conference on Artificial Neural Networks in 2018. Other open source NTM implementations exist, however they are not reliable enough for production usage. The developers either state that their implementation’s gradients occasionally become NaN during training for unexplained reasons, causing training to fail; report delayed convergence; or do not describe their implementation’s pace of learning.
Differentiable neural computers are a development of Neural Turing machines that include attention techniques that regulate where the memory is active and increase performance.
Summary
In this blog we got a brief idea about the theory of computation, we described about the finite automata and the regular expression in brief. Mainly highlighting the Pushdown Automata and Turing Machine and also decribing about the grammar used by the above machines(Context free grammar by PDA and Unrestricted Grammar by Turing Machine). Further comparing both of the machine and concluding by giving application of pushdown Automata and Turing machine.
Authors
Shaunak Mahajan, Atharva Bakde, Shantanu Avhad, Isha Korate, Rudraksha Padole