Pushdown Automata (PDA) in Computer Science
Lecture #27-28
PDA
A pushdown automata (PDA) is basically an
Є
-NFA
with a stack.
On a transition, the PDA:
1. Consumes an input symbol.
2. Goes to a new state (or stays in the old).
3. Replaces the top of the stack by any string (does
nothing, pops the stack, or pushes a string onto the
stack)
PDA
PDAs are like NFAs but have an extra component called a
stack
The stack provides additional memory beyond the finite
amount available in the control
The stack allows PDA to recognize some non-regular
languages
PDA
PDA and CFG
PDA are equivalent in specification power with
CFG
This is useful because it gives us two options
for proving that a language is context-free:
1. construct a CFG that generates the language
or
2. construct a PDA that recognizes the
language
7
Input String
Stack
States
8
Initial Stack Symbol
Stack
Stack
bottom
special symbol
stack
head
top
Appears at time 0
9
Input
symbol
Pop
symbol
Push
symbol
Push Down Automata
An NFA with a stack
Can be used to represent Context free languages
Example
PDA
A PDA is a collection of
Input Tape
States
States
State Representation
State Representation
Stack
Example
FA that accepts all words ending in the letter a
Example
Example
FA that contains at least a double aa
Example
PDA that contains at least a double aa
Stack Operations
a
n
b
n
Test
-
aaabbb
Example
Equivalent Machine is
Try the strings:
1). aaabbbb
2). aaaabbb
Example of all states
Definition
Example
CFG is
Example Cont…
Palindrome
Let us introduce the PALINDROMEX, language of all
words of the form
s X reverse(s)
where s is any string in (a + b)*
The words in this language are
{X,aXa, bXb, aaXaa, abXba, baXab, bbXbb, aaaXaaa, aabXbaa . . .
}
Palindrome Machine
Start can be like this
Palindrome Machine
Palindrome Machine (
Odd Palindrome
)
For odd palindrome (Guess middle alphabet) . The problem here is that the middle
letter does not stand out, so it is harder to recognize where the first half ends and the
second half begins. In fact, it‘s not only harder; it's impossible
Palindrome Machine (
even Palindrome
)
Palindrome Machine (
even Palindrome
)
PDA accepts language from following CFG
Example
Assignment
Solve Question # of book 1, 2, 3, 5 at page 370
Another CFG to NPDA Example
Equivalent PDA /NPDA is
Another CFG to NPDA Example
Equivalent PDA /NPDA is
Another CFG to NPDA Example
Assignment
Solve Questions 1,2,3,4,5 at page 424
Chomsky Normal Form
Chomsky Normal Form
Chomsky Normal Form
Pushdown Automata (PDA) are essential in theoretical computer science, serving as an extension of non-deterministic finite automata (NFA). PDAs incorporate a stack, enabling them to recognize non-regular languages. They are described by transitions involving input symbols, state changes, and stack manipulation. Equivalence between CFGs and PDAs offers flexibility in proving language context-freeness.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
PDA A pushdown automata (PDA) is basically an -NFA with a stack. On a transition, the PDA: 1. Consumes an input symbol. 2. Goes to a new state (or stays in the old). 3. Replaces the top of the stack by any string (does nothing, pops the stack, or pushes a string onto the stack)
PDA PDAs are like NFAs but have an extra component called a stack The stack provides additional memory beyond the finite amount available in the control The stack allows PDA to recognize some non-regular languages
PDA and CFG PDA are equivalent in specification power with CFG This is useful because it gives us two options for proving that a language is context-free: 1. construct a CFG that generates the language or 2. construct a PDA that recognizes the language
Pushdown Automaton -- PDA Input String Stack States 7
Initial Stack Symbol Stack Stack stack head $ z top bottom special symbol Appears at time 0 8
The States Push symbol Pop symbol Input symbol a, b c q1 q2 9
Push Down Automata An NFA with a stack Can be used to represent Context free languages
PDA A PDA is a collection of
Example FA that accepts all words ending in the letter a
Example FA that contains at least a double aa
Example PDA that contains at least a double aa
anbn Test - aaabbb
Equivalent Machine is Try the strings: 1). aaabbbb 2). aaaabbb
Example CFG is
Palindrome Let us introduce the PALINDROMEX, language of all words of the form s X reverse(s) where s is any string in (a + b)* The words in this language are { X,aXa, bXb, aaXaa, abXba, baXab, bbXbb, aaaXaaa, aabXbaa . . . }
Palindrome Machine Start can be like this
Palindrome Machine (Odd Palindrome) For odd palindrome (Guess middle alphabet) . The problem here is that the middle letter does not stand out, so it is harder to recognize where the first half ends and the second half begins. In fact, it s not only harder; it's impossible
Assignment Solve Question # of book 1, 2, 3, 5 at page 370
Another CFG to NPDA Example Equivalent PDA /NPDA is
Another CFG to NPDA Example Equivalent PDA /NPDA is
Assignment Solve Questions 1,2,3,4,5 at page 424
