San Pablo Colleges
College of Computer Studies
AL102 – AUTOMATA THEORY AND FORMAL LANGUAGES
Weekly Module
Prof. Apolo Joseph D. Capuno, MSIT
PUSHDOWN AUTOMATA
Credits : 3 units lecture (3 hours/week)
Pre-Requisite : 3rd year standing
Programs : BSCS
Lesson Objective:
At the end of the module, the learners will be able to:
1. Define Pushdown Automata and explain how it differs from DFA/NFA.
2. Interpret stack operations (push, pop, no-op) in PDA transitions.
3. Construct a PDA for simple Context-Free Languages.
4. Trace whether a string is accepted or rejected by a PDA.
Course Textbook:
1. Hopcroft, J.E., Motwani, R., Ullman, J.D. Introduction to Automata Theory, Languages, and
Computation.
2. Linz, P. An Introduction to Formal Languages and Automata.
3. Sipser, M. Introduction to the Theory of Computation.
Lectures and Annotations:
In the previous topic, we discussed Context-Free Grammars (CFGs) and saw how they are used
to describe Context-Free Languages, which include languages that require structure or
balancing, such as aⁿbⁿ or properly nested parentheses.
CFGs allow us to generate strings using recursive production rules, something that Regular
Grammars and Finite Automata cannot accomplish. However, while CFGs describe how such
languages are formed, they do not directly show how strings are processed or recognized by a
machine. This leads us to the next step in our study: the Pushdown Automaton (PDA).
Lesson 1.
Introduction
It is a way to implement a Context Free Grammar in a similar way to design Finite Automata for
Regular Grammar
Let us look into Noam Chomsky’s four type of grammar:
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
A Pushdown Automaton (PDA) is similar to a Finite Automaton but with memory, stored in
the form of a stack.
Machine Memory Structure Power (Language Class)
Recognizes Regular
DFA / NFA No memory
Languages
Recognizes Context-Free
PDA Stack (LIFO) memory
Languages
Why Do We Need a Stack?
Finite automata cannot count or remember more than a fixed amount.
Example: The language
𝐿 = {𝑎𝑛 𝑏𝑛 ∣ 𝑛 > 0}
requires remembering how many a’s appeared to match them with b’s.
→ DFA cannot do this.
→ PDA can, because it pushes a’s in the stack, then pops one per b.
PDA = Finite State Machine + STACK
What is a STACK?
A stack is a way we arrange elements one on top of another
A stack does two basic operations:
PUSH: A new element is added at the Top of the stack
POP: The Top element of the stack is read and removed
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
Operations of Stack:
Adding an element: TOP
Removing an element: POP
Visual Representation of PUSH DOWN AUTOMATA:
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
Lesson 2
Formal Definition of a PDA
A PDA is defined as a 7-tuple:
𝑀 = (𝑄, Σ, Γ, 𝛿, 𝑞0 , 𝑍0 , 𝐹)
Where:
Symbol Meaning
𝑄 A final set of States /Set of States
Σ A finite set of Input Symbols
Γ A finite Stack Alphabet
𝛿 The Transition Function
𝑞0 The Start State
𝑍0 The Initial/ Start Stack Symbol
𝐹 Accepting States
Let us take a closer look at the Transition Function of the Pushdown Automata:
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
Lesson 3
Graphical Notation of Pushdown Automata
Deep explanation of the components of PDA
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
Let us look into an example:
This is a PDA that accepts L = {0𝑛 1𝑛 | 𝑛 ≥ 0}
Similar to: 𝑎𝑛 𝑏𝑛
Say it accepts the strings: 0011
From Starting state q1
We have an input:
∈, ∈ → Z0
So our stack currently must look like this
Current Stack
Z0
Then we transitioned to q2
From: 0011
0, ∈ → 0
Current Stack
0
Z0
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
Then we transitioned to q2 again
From: 0011
0, ∈ → 0
Current Stack
0
0
Z0
Then we transitioned to q3
From: 0011
1, 0 → ∈
Current Stack
0
0
Z0
1, 0 → ∈ // 0 is popped
Current Stack
0
Z0
Then we transitioned to q3 again
From: 0011
1, 0 → ∈
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
0
Z0
1, 0 → ∈ // 0 is popped again
Current Stack
Z0
From the previous state q3
We have an input:
∈, Z0 → ∈
Current Stack
Z0
∈, Z0 → ∈// Z0 is compared and popped from the stack
Current Stack
We have now reached the final state q4
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC
San Pablo Colleges
College of Computer Studies
Therefore, the strings 0011 is accepted
There are two scenarios where the language/ strings are accepted with Pushdown Automata
1. We have reached the Final State
2. The Stack is Empty.
From the previous example: both of the scenarios are true.
- End of the module
Hermanos Belen St., San Pablo City
+63 936 123 6745 | [Link]@[Link]
[Link]/ComputerStudiesSPC