BU CS 332 – Theory of Computation
Lecture 8:
• Equivalence between PDAs and CFGs
• Closure Properties
Mark Bun February 18, 2020
Reading: Sipser Ch 2.2
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 𝑎𝑎𝑏𝑏𝑎𝑎𝑎𝑎
𝑥𝑥𝑥𝑥 𝑦𝑦
…
Finite control
Transitions of the form:
𝑝𝑝 𝑎𝑎,𝑥𝑥 → 𝑥𝑥𝑥 𝑞𝑞
Memory: Infinite Stack
2/17/2020 CS332 – Theory of Computation 2
Example: Even Palindromes
𝑞𝑞0
𝑞𝑞
𝜀𝜀,𝜀𝜀 → $ 𝜀𝜀,$ → 𝜀𝜀
𝑝𝑝 𝑞𝑞
𝑎𝑎,𝜀𝜀 → 𝑎𝑎 𝑏𝑏,𝜀𝜀 →𝑏𝑏
𝑓𝑓
𝑎𝑎,𝑎𝑎→ 𝜀𝜀 𝑏𝑏,𝑏𝑏→ 𝜀𝜀
𝜀𝜀,𝜀𝜀→ 𝜀𝜀
2/18/2020
CS332 – Theory of Computation
3
Pushdown Automaton (formal)
A PDA is a 6-tuple 𝑀𝑀 = (𝑄𝑄,Σ,Γ,𝛿𝛿,𝑞𝑞0,𝐹𝐹) • 𝑄𝑄 is a finite set of states
• Σ is the input alphabet
• Γ is the stack alphabet
• 𝛿𝛿:𝑄𝑄 × Σ𝜀𝜀 × Γ𝜀𝜀 →𝑃𝑃(𝑄𝑄× Γ𝜀𝜀)isthetransitionfunction • 𝑞𝑞0 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/17/2020 CS332 – Theory of Computation 4
𝐿𝐿 = {𝑤𝑤|𝑤𝑤 has an equal number of 𝑎𝑎’s and 𝑏𝑏’s} Algorithmic description
Example
2/18/2020 CS332 – Theory of Computation 5
𝐿𝐿 = {𝑤𝑤|𝑤𝑤 has an equal number of 𝑎𝑎’s and 𝑏𝑏’s} State diagram
Example
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/17/2020 CS332 – Theory of Computation 7
CFG -> PDA
2/17/2020 CS332 – Theory of Computation 8
CFG -> PDA Conversion
Supposelanguage𝐿𝐿isgeneratedbyCFG𝐺𝐺 = 𝑉𝑉,Σ,𝑅𝑅,𝑆𝑆 Goal: Construct a PDA 𝑀𝑀 = (𝑄𝑄, Σ, Γ, 𝛿𝛿, 𝑞𝑞0, 𝐹𝐹) 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/17/2020 CS332 – Theory of Computation 9
Algorithmic Description
1. 2.
Place $ and the start variable 𝑆𝑆 on the stack
Repeat forever:
a) If the top of the stack holds variable 𝐴𝐴:
Nondeterministically guess a rule 𝐴𝐴 → 𝑢𝑢 ∈ 𝑅𝑅 Replace 𝐴𝐴 with 𝑢𝑢 on the stack
b) If the top of the stack holds terminal 𝜎𝜎:
Pop 𝜎𝜎 and verify that it matches the next input char
c) If the top of the stack holds $: Accept if the input is empty
2/17/2020 CS332 – Theory of Computation 10
State Diagram
𝜀𝜀,𝜀𝜀→𝑆𝑆𝑆 𝑞𝑞0 𝜀𝜀,$ → 𝜀𝜀𝑞𝑞𝑙𝑙𝑙𝑙𝑙𝑙𝑝𝑝
𝑞𝑞𝑓𝑓
𝜀𝜀,𝐴𝐴 →𝑢𝑢 [foreveryrule𝐴𝐴→𝑢𝑢] 𝜎𝜎,𝜎𝜎 → 𝜀𝜀 [for every terminal 𝐴𝐴 → 𝜎𝜎]
2/17/2020
CS332 – Theory of Computation 11
Example
𝑆𝑆 → 𝑎𝑎𝑇𝑇𝑏𝑏 𝑇𝑇 → 𝑇𝑇𝑎𝑎|𝜀𝜀
𝜀𝜀,𝜀𝜀→𝑆𝑆𝑆 𝑞𝑞0 𝜀𝜀,$ → 𝜀𝜀𝑞𝑞𝑙𝑙𝑙𝑙𝑙𝑙𝑝𝑝
2/17/2020
𝑞𝑞𝑓𝑓
CS332 – Theory of Computation 12
Example
𝑆𝑆 → 𝑎𝑎𝑇𝑇𝑏𝑏 𝑇𝑇 → 𝑇𝑇𝑎𝑎|𝜀𝜀
𝜀𝜀,$ → 𝜀𝜀𝑞𝑞𝑙𝑙𝑙𝑙𝑙𝑙𝑝𝑝 2/18/2020 𝑞𝑞𝑓𝑓
CS332 – Theory of Computation 13
𝑞𝑞0
PDA -> CFG
2/17/2020 CS332 – Theory of Computation 14
PDA -> CFG Conversion
Theorem 2: Every PDA has an equivalent CFG
Suppose 𝐿𝐿 is recognized by PDA 𝑀𝑀 = (𝑄𝑄,Σ,Γ,𝛿𝛿,𝑞𝑞 ,𝐹𝐹)
Goal:ConstructaCFG𝐺𝐺 = 𝑉𝑉,Σ,𝑅𝑅,𝑆𝑆 generating𝐿𝐿
First simplify 𝑀𝑀 so that:
1. It has a single accept state 𝑞𝑞𝑓𝑓
2. It empties the stack before accepting
3. Every transition either pushes a symbol or pops a symbol (but not both)
2/17/2020 CS332 – Theory of Computation 15
0
Simplification Example
𝑎𝑎, 𝜀𝜀 → 𝑎𝑎 𝑝𝑝 𝑏𝑏,𝜀𝜀 →𝑏𝑏
𝑞𝑞0 𝜀𝜀,𝜀𝜀 → $
𝜀𝜀,𝜀𝜀→ 𝜀𝜀
𝑞𝑞
𝑓𝑓
𝜀𝜀,$ → 𝜀𝜀
𝑞𝑞 𝑎𝑎,𝑎𝑎→ 𝜀𝜀 𝑏𝑏,𝑏𝑏→ 𝜀𝜀
2/17/2020 CS332 – Theory of Computation
16
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/17/2020 CS332 – Theory of Computation 17
Example
𝑞𝑞0 𝜀𝜀,𝜀𝜀 → $ 𝜀𝜀, 𝜀𝜀 → #
𝑎𝑎,𝜀𝜀 → 𝑎𝑎 𝑞𝑞 𝑏𝑏,𝜀𝜀 →𝑏𝑏
𝑞𝑞
What strings should 𝐴𝐴𝑝𝑝0𝑝𝑝1generate?
1 𝜀𝜀,𝜀𝜀→# 𝑞𝑞2 𝜀𝜀,#→𝜀𝜀
5
𝜀𝜀,𝜀𝜀→# 𝜀𝜀,$→𝜀𝜀 𝑞𝑞4
𝑞𝑞 𝑎𝑎,𝑎𝑎→ 𝜀𝜀 3 𝑏𝑏,𝑏𝑏→ 𝜀𝜀
What strings should 𝐴𝐴𝑝𝑝1𝑝𝑝3generate? What strings should 𝐴𝐴𝑝𝑝1𝑝𝑝4generate?
2/18/2020 CS332 – Theory of Computation
18
What rules should define 𝐴𝐴𝑝𝑝𝑝𝑝? Let 𝑥𝑥 be a string generated by 𝐴𝐴𝑝𝑝𝑝𝑝
Two cases:
1) Stack first empties after reading all of 𝑥𝑥
stack height
2) Stack empties before reaching the end of 𝑥𝑥 stack
input string
𝑝𝑝𝑞𝑞
height
input string
𝑝𝑝𝑞𝑞
2/17/2020
CS332 – Theory of Computation 19
1. Stack first empties after reading all of 𝑥𝑥
stack height
input string
𝑎𝑎𝑟𝑟 𝑠𝑠𝑏𝑏 𝑝𝑝𝑞𝑞
2/17/2020
Add rule 𝐴𝐴𝑝𝑝𝑝𝑝 → 𝑎𝑎𝐴𝐴𝑟𝑟𝑟𝑟𝑏𝑏
CS332 – Theory of Computation 20
2. Stack empties before reaching the end of 𝑥𝑥 stack
height
𝑝𝑝𝑟𝑟𝑞𝑞 Add rule 𝐴𝐴𝑝𝑝𝑝𝑝 → 𝐴𝐴𝑝𝑝𝑟𝑟𝐴𝐴𝑟𝑟𝑝𝑝
input string
2/17/2020
CS332 – Theory of Computation 21
Formal CFG Construction
𝑉𝑉=𝐴𝐴𝑝𝑝𝑝𝑝 𝑝𝑝,𝑞𝑞∈𝑄𝑄}
𝑆𝑆 = 𝐴𝐴𝑝𝑝0𝑝𝑝𝑓𝑓
1.Forevery𝑝𝑝,𝑞𝑞,𝑟𝑟,𝑠𝑠∈𝑄𝑄, 𝑡𝑡∈Γ, 𝑎𝑎,𝑏𝑏∈Σ :
Three kinds of rules:
𝜀𝜀
If (𝑟𝑟,𝑡𝑡) ∈ 𝛿𝛿(𝑝𝑝,𝑎𝑎,𝜀𝜀) and (𝑞𝑞,𝜀𝜀) ∈ 𝛿𝛿(𝑠𝑠,𝑏𝑏,𝑡𝑡), include the rule 𝐴𝐴𝑝𝑝𝑝𝑝 → 𝑎𝑎𝐴𝐴𝑟𝑟𝑟𝑟𝑏𝑏
2. For every 𝑝𝑝, 𝑞𝑞, 𝑟𝑟 ∈ 𝑄𝑄, include the rule 𝐴𝐴𝑝𝑝𝑝𝑝 → 𝐴𝐴𝑝𝑝𝑟𝑟𝐴𝐴𝑟𝑟𝑝𝑝 3. For every 𝑝𝑝 ∈ 𝑄𝑄, include the rule 𝐴𝐴𝑝𝑝𝑝𝑝 → 𝜀𝜀
2/17/2020 CS332 – Theory of Computation 22
Sketch of proof that CFG generates 𝐿𝐿(𝑀𝑀) Claim:𝐴𝐴𝑝𝑝𝑝𝑝 ⇒∗ 𝑥𝑥ifandonlyif𝑥𝑥takes𝑀𝑀from𝑝𝑝to𝑞𝑞,
beginning and ending with empty stack
⟹ Induction on number of steps of derivation of 𝑥𝑥 from 𝐴𝐴𝑝𝑝𝑝𝑝
Proof idea:
⟸ 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/17/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/17/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/17/2020 CS332 – Theory of Computation 27
2/18/2020 CS332 – Theory of Computation 28
𝑞𝑞0 1, 𝜀𝜀 → 0 𝑞𝑞1
1,𝜀𝜀→1 𝑞𝑞2 𝜀𝜀,𝜀𝜀→$ 𝑞𝑞0
𝑎𝑎,𝜀𝜀→𝑎𝑎 𝑞𝑞 𝑏𝑏,𝜀𝜀 →𝑏𝑏
𝑞𝑞5
𝜀𝜀,𝜀𝜀→#
1 𝜀𝜀,𝜀𝜀→# 𝑞𝑞2 𝜀𝜀,#→𝜀𝜀
2/18/2020
𝑞𝑞 4
𝜀𝜀,𝜀𝜀→# 𝜀𝜀,$ → 𝜀𝜀
𝑞𝑞 𝑎𝑎,𝑎𝑎→ 𝜀𝜀 3 𝑏𝑏,𝑏𝑏→ 𝜀𝜀
CS332 – Theory of Computation
29