Introduction of Pushdown Automata
We have already discussed finite automata. But finite automata can be used to accept only
regular languages. Pushdown Automata is a finite automata with extra memory called stack
which helps Pushdown automata to recognize Context Free Languages. This article describes
pushdown automata in detail.
Pushdown Automata
A Pushdown Automata (PDA) can be defined as:
• Q is the set of states
• ∑is the set of input symbols
• Γ is the set of pushdown symbols (which can be pushed and popped from the stack)
• q0 is the initial state
• Z is the initial pushdown symbol (which is initially present in the stack)
• F is the set of final states
• δ is a transition function that maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In each state, the PDA
will read the input symbol and stack symbol (top of the stack) move to a new state, and
change the symbol of the stack.
Example: Define the pushdown automata for language {anbn | n > 0}
Solution: M = where Q = {q0, q1} and Σ = {a, b} and Γ = {A, Z} and δ is given by:
δ( q0, a, Z ) = { ( q0, AZ ) }
δ( q0, a, A) = { ( q0, AA ) }
δ( q0, b, A) = { ( q1, ∈) }
δ( q1, b, A) = { ( q1, ∈) }
δ( q1, ∈, Z) = { ( q1, ∈) }
Let us see how this automata works for aaabbb.
Explanation: Initially, the state of automata is q0 and symbol on stack is Z and the input is
aaabbb as shown in row 1. On reading ‘a’ (shown in bold in row 2), the state will remain q0
and it will push symbol A on stack. On next ‘a’ (shown in row 3), it will push another symbol
A on stack. After reading 3 a’s, the stack will be AAAZ with A on the top. After reading ‘b’ (as
shown in row 5), it will pop A and move to state q1 and stack will be AAZ. When all b’s are
read, the state will be q1 and stack will be Z. In row 8, on input symbol ‘∈’ and Z on stack, it
will pop Z and stack will be empty. This type of acceptance is known as acceptance by empty
stack.
Push Down Automata State Diagram:
State Diagram for above Push Down Automata
Note:
• The above pushdown automaton is deterministic in nature because there is only one
move from a state on an input symbol and stack symbol.
• The non-deterministic pushdown automata can have more than one move from a state
on an input symbol and stack symbol.
• It is not always possible to convert non-deterministic pushdown automata to
deterministic pushdown automata.
• The expressive power of non-deterministic PDA is more as compared to expressive
deterministic PDA as some languages are accepted by NPDA but not by deterministic
PDA which will be discussed in the next article.
• The pushdown automata can either be implemented using acceptance by empty stack
or acceptance by final state and one can be converted to another.
Question: Which of the following pairs have DIFFERENT expressive power?
A. Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
B. Deterministic push down automata (DPDA)and Non-deterministic push down automata
(NPDA)
C. Deterministic single-tape Turing machine and non-deterministic single-tape Turing
machine
D. Single-tape Turing machine and the multi-tape Turing machine
Solution: Every NFA can be converted into DFA. So, there expressive power is same. As
discussed above, every NPDA can’t be converted to DPDA. So, the power of NPDA and DPDA
is not the same. Hence option (B) is correct.
Conclusion
In conclusion, Pushdown Automata (PDA) are an important concept in computer science and
formal language theory. They extend the capabilities of finite automata by using a stack, which
allows them to handle a broader range of languages, particularly context-free languages. PDAs
can recognize patterns and structures that simpler models cannot, making them essential for
parsing and processing languages in compilers and other applications. Understanding PDAs
helps in grasping how more complex systems operate and enhances our knowledge of
computation and algorithms.
Applications of various Automata
Automata is a machine that can accept the Strings of a Language L over an input alphabet Σ.
So far, we are familiar with the Types of Automata. Now, let us discuss the expressive power
of Automata and further understand its applications.
The Applications of various Automata are given as follows:
1. Finite Automata (FA)
Finite Automata are widely used in several applications:
• Lexical Analysis in Compilers: FA helps identify keywords, operators, and tokens in
source code.
• Pattern Recognition with Regular Expressions: FA models regular expressions used
for searching and matching patterns in text files (e.g., using tools like grep).
• Digital Circuit Design: FA is used in the design of sequential circuits, such as Mealy
and Moore machines.
• Text Editors: Used to find and replace patterns in large text files.
• Spell Checkers: FA can be used to recognize valid word forms in spelling applications.
• Decision Making and Learning: Can be modelled to help automate decision-making
processes.
2. Push Down Automata (PDA)
Pushdown Automata are utilized in:
• Syntax Analysis in Compilers: Helps parse programming language structures by using
a stack to manage nested elements (e.g., parentheses).
• Stack-Based Applications: Used in scenarios where operations depend on the last
inserted element, like evaluating arithmetic expressions.
• Tower of Hanoi Problem: Solves problems involving recursive and stack-based
solutions.
• Network Protocols: PDA can validate message formats and enforce structured
communication.
• Natural Language Processing: Used in tasks such as parsing sentences and generating
syntax trees.
• Cryptography: Helps in designing algorithms for encryption and decryption.
• Automatic Theorem Proving: PDA is applied to verify the correctness of software
models and systems.
3. Linear Bounded Automata (LBA)
Linear Bounded Automata are useful in:
• Genetic Programming: Helps model evolutionary algorithms in genetics.
• Semantic Analysis in Compilers: Constructs syntactic parse trees to analyze code
semantics.
• Context-Sensitive Language Recognition: Used for languages that require more
computational power than context-free languages.
• Game Theory: Models interactions between agents and studies strategic behavior.
4. Turing Machine (TM)
Turing Machines, being the most powerful automaton, have extensive applications:
• Solving Recursively Enumerable Problems: TM can solve any problem that is
recursively enumerable.
• Artificial Intelligence: Forms the foundation of AI algorithms, including decision-
making and machine learning.
• Robotics: Used to model robot actions and control systems.
• Neural Networks: TM can model complex neural networks.
• Complexity Theory: Used to analyze the computational complexity of algorithms.
• Computational Biology: Applied to model biological processes and systems.
• Quantum Computing: Provides insights into the relationship between classical and
quantum computing models.
• Digital Circuit Design: Used to model and verify the behavior of complex digital
circuits.