BU CS 332 – Theory of Computation
Lecture 7:
• More on CFGs
Reading:
Sipser Ch 2.1‐2.3
• Pushdown Automata
Mark Bun February 12, 2020
Context‐Free Grammar (Formal)
A CFG is a 4‐tuple
• • •
is a finite set of variables
is a finite set of terminal symbols (disjoint from
)
,
•
is a finite set of production rules of the form
where
and
is the start symbol
∗
2/12/2020
CS332 ‐ Theory of Computation
2
Context‐Free Grammar
Example Grammar
Parse Tree
Derivation
2/12/2020
CS332 ‐ Theory of Computation
3
|| |
Context‐Free Languages
𝐿 is a context‐free language if it is the language of some CFG
2. How do we recognize whether 𝑤 ∈ 𝐿?
2/12/2020
CS332 ‐ Theory of Computation 4
Questions about CFLs
1. Which languages are not context‐free?
3. What are the closure properties of CFLs?
Pumping Lemma for context‐free languages
Let be a context‐free language. Then there exists a “pumping length”
such that where:
For every where , can be split into five parts
1.
2.
3. 𝑖 𝑖 forall
2/12/2020 CS332 ‐ Theory of Computation
5
Pumping Lemma example
Claim: Proof: Assume
is not context‐free
is context‐free with pumping length
1. Find
2. Show that
with
cannot be pumped
If =
Case 1: both contain only one kind of symbol Case 2: Either or contains two kinds of symbols
with | | , then…
2/12/2020 CS332 ‐ Theory of Computation 6
Pumping Lemma example
Claim: Proof: Assume
is not context‐free
is context‐free with pumping length
1. Find
2. Show that
with
cannot be pumped
If =
with | | , then… both contain only one kind of symbol
Case 1:
2/12/2020
CS332 ‐ Theory of Computation 7
2/12/2020 CS332 ‐ Theory of Computation 8
Pumping Lemma example
Claim: Proof: Assume
is not context‐free
is context‐free with pumping length
1. Find with
2. Show that cannot be pumped
If = with | | , then…
Case 2: Either
or contains two kinds of symbols
2/12/2020
CS332 ‐ Theory of Computation 9
Pumping Lemma: Proof idea
Let be a context‐free language. If is long enough, then every parse tree for has a repeated variable.
2/12/2020 CS332 ‐ Theory of Computation 10
Pumping Lemma Proof
What does “long enough” mean? (How do we choose the pumping length ?)
•Let beaCFGfor
• Suppose the right‐hand side of every rule in most symbols
uses at
for has height at least
• Let
Claim: If with , then the smallest parse tree
2/12/2020 CS332 ‐ Theory of Computation 11
Pumping Lemma Proof
Claim: If with , then the smallest parse tree for has height at least
• By the pigeonhole principle, there is a path down the parse tree with a repeated variable 𝑅
• Choose two such occurrences within the bottom 𝑉 1 levels
2/12/2020 CS332 ‐ Theory of Computation 12
Context‐Free Languages
𝐿 is a context‐free language if it is the language of some CFG
2. How do we recognize whether 𝑤 ∈ 𝐿?
2/12/2020
CS332 ‐ Theory of Computation 13
Questions about CFLs
1. Which languages are not context‐free?
3. What are the closure properties of CFLs?
Pushdown Automata
2/12/2020 CS332 ‐ Theory of Computation 14
Regular Expressions : Finite Automata :: Context‐Free Languages : ???
2/12/2020 CS332 ‐ Theory of Computation 15
Pushdown Automata
Input
𝑎 𝑏 𝑎 𝑎 … Finite
Finite Automata (FAs): Machine with a finite amount of unstructured memory
Input 𝑎𝑏𝑎𝑎
… Pushdown Automata (PDAs): Machine with unbounded structured memory in the
2/12/2020
CS332 ‐ Theory of Computation 16
control
Finite control
𝑥 𝑥 𝑦
form of a stack Memory: Infinite Stack
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/12/2020
CS332 ‐ Theory of Computation
17
Finite control
𝑥 𝑥 𝑦
𝑎,𝑥 → 𝑥′
Memory: Infinite Stack
Example: Even Palindromes
2/12/2020
CS332 ‐ Theory of Computation 18
∗
Input
𝑎𝑏𝑏𝑏𝑏𝑎
…
Finite control
Memory: Infinite Stack
Example: Even Palindromes
∗
Algorithmic Description
1. Place the marker $ on the stack
2. Nondeterministically, either
Memory: Infinite Stack
Input
𝑎𝑏𝑏𝑏𝑏𝑎
…
a) Read a character and push it to the stack, or
b) Go to the next step
3. Nondeterministically, either
a) Pop the stack if it matches the next character or
b) Go to the next step
4. Accept if the top of the stack is $
2/12/2020 CS332 ‐ Theory of Computation
19
Finite control
Example: Even Palindromes
2/12/2020
CS332 ‐ Theory of Computation
20
𝜀,𝜀 → $ 0
𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏
𝜀,$ → 𝜀 𝑓
𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀
𝜀,𝜀→ 𝜀
Pushdown Automaton (formal)
A PDA is a 6‐tuple (sorry)
• • •
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/12/2020 CS332 ‐ Theory of Computation 21
Example: Even Palindromes
2/12/2020
CS332 ‐ Theory of Computation 22
𝜀,𝜀 → $ 0
𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏
𝜀,$ → 𝜀 𝑓
𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀
𝜀,𝜀→ 𝜀
𝛿 : 𝑄 Σ Γ → 𝑃 𝑄 Γ
𝛿 𝑝,𝑏,𝜀 𝛿 𝑞,𝑎,𝑎 𝛿 𝑞,𝑎,𝑏