BU CS 332 – Theory of Computation
Lecture 8:
• Equivalence between PDAs and CFGs
Reading: Sipser Ch 2.2
• Closure Properties
Mark Bun February 18, 2020
Pushdown Automaton (the idea)
• Nondeterministic finite automaton + stack
• Stack has unlimited size, but machine can only manipulate (push,
pop, read) symbol at the top Input 𝑎𝑏𝑎𝑎
…
Transitions of the form:
2/18/2020
CS332 ‐ Theory of Computation
2
Finite control
𝑥 𝑥 𝑦
𝑎,𝑥 → 𝑥′
Memory: Infinite Stack
Example: Even Palindromes
2/18/2020
CS332 ‐ Theory of Computation
3
𝜀,𝜀 → $ 0
𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏
𝜀,$ → 𝜀 𝑓
𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀
𝜀,𝜀→ 𝜀
Pushdown Automaton (formal)
A PDA is a 6‐tuple
• • •
is a finite set of states is the input alphabet is the stack alphabet
• :
is the transition function
• •
is the start state
is the set of final states
accepts a string if, starting from 0 and an empty stack, there exists a path to an accept state that can be followed by reading all of .
2/18/2020 CS332 ‐ Theory of Computation 4
Example
has an equal number of ’s and ’s
Algorithmic description
2/18/2020 CS332 ‐ Theory of Computation
5
Example
State diagram
has an equal number of ’s and ’s
2/18/2020 CS332 ‐ Theory of Computation
6
CFGs vs. PDAs
The language of a PDA is the set of all strings it accepts.
Theorem: The class of languages recognized by PDAs is exactly the context‐free languages.
Theorem 1: Every CFG has an equivalent PDA Theorem 2: Every PDA has an equivalent CFG
2/18/2020 CS332 ‐ Theory of Computation 7
CFG ‐> PDA
2/18/2020 CS332 ‐ Theory of Computation 8
CFG ‐> PDA Conversion
Suppose language is generated by CFG = Goal: Construct a PDA
recognizing
Idea: will guess the steps of the CFG derivation of its input , and use its stack to check the derivation
A helpful intermediate abstraction
Generalized PDA: Can push an entire string to the stack in one move
2/18/2020 CS332 ‐ Theory of Computation 9
Algorithmic Description
1.
Place and the start variable on the stack Repeat forever:
2.
a)
If the top of the stack holds variable : Nondeterministically guess a rule Replace with on the stack
b) c)
If the top of the stack holds terminal :
Pop and verify that it matches the next input char
If the top of the stack holds : Accept if the input is empty
2/18/2020 CS332 ‐ Theory of Computation 10
State Diagram
0 𝜀, 𝜀 → 𝑆$
𝑙𝑜𝑜𝑝 𝜀, $ → 𝜀
𝜀,𝐴 → 𝑢 𝜎,𝜎 → 𝜀
[foreveryrule𝐴 → 𝑢] [for every terminal 𝐴 → 𝜎]
2/18/2020
CS332 ‐ Theory of Computation 11
𝑓
Example
0 𝜀, 𝜀 → 𝑆$
𝑙𝑜𝑜𝑝 𝜀, $ → 𝜀
2/18/2020
CS332 ‐ Theory of Computation 12
𝑓
Example
𝑙𝑜𝑜𝑝 𝜀, $ → 𝜀
2/18/2020
CS332 ‐ Theory of Computation 13
0
𝑓
PDA ‐> CFG
2/18/2020 CS332 ‐ Theory of Computation 14
PDA ‐> CFG Conversion
Theorem 2: Every PDA has an equivalent CFG Suppose is recognized by PDA
Goal: Construct a CFG = First simplify so that:
generating
1. 2. 3.
It has a single accept state
It empties the stack before accepting
Every transition either pushes a symbol or pops a symbol (but not both)
2/18/2020 CS332 ‐ Theory of Computation 15
𝑓
Simplification Example
2/18/2020
CS332 ‐ Theory of Computation 16
𝜀,𝜀 → $ 0
𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏
𝜀,$ → 𝜀 𝑓
𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀
𝜀,𝜀→ 𝜀
Conversion Idea
Variables: for every pair of states in PDA Idea: generates all strings that can take from
(with an empty stack) to (with an empty stack)
2/18/2020 CS332 ‐ Theory of Computation 17
Example 𝜀,𝜀 → $ 0
1
𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏
6
5
2
𝜀,# →𝜀
𝜀, 𝜀 → #
𝜀, 𝜀 → #
What strings should 𝐴 generate? What strings should 𝐴 generate?
What strings should 𝐴 generate?
2/18/2020 CS332 ‐ Theory of Computation
18
𝜀, 𝜀 → #
𝜀, # → 𝜀
𝜀,$ → 𝜀 4
3
𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀
What rules should define ?
Let be a string generated by Two cases:
2/18/2020
CS332 ‐ Theory of Computation 19
1) Stack first empties after reading all of stack
input string
𝑝𝑞
height
2) Stack empties before reaching the end of stack
input string
𝑝𝑞
height
1. Stack first empties after reading all of
input string
2/18/2020
CS332 ‐ Theory of Computation
20
stack height
Add rule
2. Stack empties before reaching the end of
input string
2/18/2020
CS332 ‐ Theory of Computation 21
stack height
Add rule
Formal CFG Construction
Three kinds of rules:
1. For every :
If and ,
include the rule 2. For every
3. For every 2/18/2020
include the rule
include the rule
CS332 ‐ Theory of Computation
22
Sketch of proof that CFG generates
Claim: ∗ if and only if takes from to , beginning and ending with empty stack
Proof idea:
Induction on number of steps of derivation of
from
Induction on number of steps of computation taking from to
2/18/2020 CS332 ‐ Theory of Computation 23
Closure Properties
2/18/2020 CS332 ‐ Theory of Computation 24
Closure Properties
• The class of CFLs is closed under Union
Concatenation
Star
Intersection with regular languages
• Beware: It is not closed under intersection or complement (Find counterexamples!)
2/18/2020 CS332 ‐ Theory of Computation 25
Closure under union (Proof 1)
Let be a CFL recognized by PDA and let
be a CFL
recognized by PDA
Goal: Construct a PDA recognizing
2/18/2020 CS332 ‐ Theory of Computation
26
Closure under union (Proof 2)
Let be a CFL generated by CFG and let
be a CFL
recognized by CFG
Goal: Construct a CFG recognizing
= =
Relabel variables so and are disjoint Let =
2/18/2020 CS332 ‐ Theory of Computation
27