CSE 305

Lecture 26
Pushdown Automata (1)
Md. Mijanur Rahman, Prof. Dr.
Dept. of Computer Science and Engineering, Jatiya Kabi Kazi Nazrul Islam University, Bangladesh.
www.mijanrahman.com

1
 Contents
Pushdown Automata

 Pushdown Automata (PDA)  PDA Acceptance

 Components of PDA  Non-deterministic PDA
 Formal Definition of PDA  PDA & CFG
 Instantaneous Description and Notation
 Examples

2
Pushdown Automata (PDA)
• Pushdown automata is a way to implement a CFG in the same way we design DFA for a
regular grammar. A DFA can remember a finite amount of information, but a PDA can
remember an infinite amount of information.
• Pushdown automata is simply an NFA augmented with an "external stack memory". The
addition of stack is used to provide a last-in-first-out memory management capability to
Pushdown automata.
• Pushdown automata can store an unbounded amount of information on the stack. It can access
a limited amount of information on the stack.
• A PDA can push an element onto the top of the stack and pop off an element from the top of the
stack. To read an element into the stack, the top elements must be popped off and are lost.

3
Pushdown Automata (PDA)
• A pushdown automaton is a way to implement a context-free grammar in a similar way we
design DFA for a regular grammar.
• A PDA is more powerful than FA. Any language which can be acceptable by FA can also be
acceptable by PDA. PDA also accepts a class of language which even cannot be accepted by
FA. Thus PDA is much more superior to FA.

• It is a finite automata with stack which helps Pushdown automata to recognize Context Free
Languages. A DFA can remember a finite amount of information, but a PDA can remember an
infinite amount of information.

4
Pushdown Automata (PDA)
• Basically a pushdown automaton is −
"Finite state machine" + "a stack“

• The stack head scans the top symbol of the stack. A stack does two operations −
• Push − a new symbol is added at the top.
• Pop − the top symbol is read and removed.

• A PDA may or may not read an input symbol, but it has to read the top of the stack in every
transition.

5
Components of PDA
• The following figure shows schematic
diagram of PDA.
PDA Components:
• Input tape: The input tape is divided in many cells
or symbols. The input head is read-only and may
only move from left to right, one symbol at a time.
• Finite control: The finite control has some pointer
which points the current symbol which is to be read.
• Stack: The stack is a structure in which we can push
and remove the items from one end only. It has an
infinite size. In PDA, the stack is used to store the
items temporarily.

6
Formal Definition of PDA

Formal definition of PDA:

• The PDA can be defined as a collection of 7 components, such as a PDA is defined by M = {Q,
∑, Γ, δ, q0, Z, F}, where:
Q: the finite set of states
∑: the input set
Γ: a stack symbol which can be pushed and popped from the stack
δ: mapping function which is used for moving from current state to next state.
q0: the initial state
Z: a start symbol which is in Γ.
F: a set of final states

7
Transition in a PDA

Transition Function of PDA:

• δ: mapping function which is used for moving from current state to next state.
• It maps Q  {Σ ∪ ∈}  Γ into Q  Γ*.
• In a given state, PDA will read input symbol and stack symbol (top of the stack) and
move to a new state and change the symbol of stack.

8
Transition in a PDA
• The following diagram shows a transition in a PDA from a state q1 to state q2, labeled
as a, b → c.

• This means at state q1, if we encounter an input string ‘a’ and top symbol of the stack
is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2.

9
Instantaneous Description

• Instantaneous Description (ID) is an informal notation of how a PDA “computes” a

input string and make a decision that string is accepted or rejected.
• A ID is a triple (q, w, α), where:
1. q is the current state.
2. w is the remaining input.
3. α is the stack contents, top at the left.

10
Turnstile Notation

• ⊢ sign is called a “turnstile notation” and represents one move.

• ⊢* sign represents a sequence of moves.
For example, (p, b, T) ⊢ (q, w, α)
• This implies that while taking a transition from state p to state q, the input symbol ‘b’
is consumed, and the top of the stack ‘T’ is replaced by a new string ‘α’

11
Example: Pushdown Automata(PDA)
Example-1 : Design a PDA for accepting a language {anb2n | n>=1}.

• Solution: In this language, n number of a's should be followed by 2n number of b's. Hence, we will apply a very
simple logic, and that is if we read single 'a', we will push two a's onto the stack. As soon as we read 'b' then for
every single 'b' only one 'a' should get popped from the stack.
• The ID can be constructed as follows:
δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
• Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence,
δ(q0, b, a) = (q1, ε)
• Thus this process of popping 'b' will be repeated unless all the symbols are read. Note that popping action occurs in
state q1 only.
δ(q1, b, a) = (q1, ε)
• After reading all b's, all the corresponding a's should get popped. Hence when we read ε as input symbol then there
should be nothing in the stack. Hence the move will be:
δ(q1, ε, Z) = (q2, ε) 12
Example: Pushdown Automata(PDA)
• Thus, the PDA, M = {Q, ∑, Γ, δ, q0, Z, F}, where Q = {q0, q1, q2} and Σ = { a, b }, Γ = {a, Z}, F=
{q2} and δ is given by the following ID:
δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (q2, ε)

• Now we will simulate this PDA for the input string "aaabbbbbb".

13
Example: Pushdown Automata(PDA)
• Example-2 : Design a PDA for accepting a language {0n1m 0n | m, n>=1}.

• Solution: In this PDA, n number of 0's are followed by any number of 1's followed n number of 0’s.
Hence the logic for design of such PDA will be as follows:
• Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then read 0, and
on each read of 0, pop one 0 from the stack.
• For instance:

14
Example: Pushdown Automata(PDA)
• This scenario can be written in the ID form as:

• Now we will simulate this PDA for the input string "0011100".

15
Example: Pushdown Automata(PDA)
• Example-3: Define the pushdown automata for language {anbn | n > 0}

• Solution : Say, M = {Q, ∑, Γ, δ, q0, Z, F}, 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 the string “aaabbb”.

16
 Example: Pushdown Automata(PDA)
• Let us see how this automata works for the string “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. 17
?
THE END

18