CS代考计算机代写 algorithm BU CS 332 – Theory of Computation

BU CS 332 – Theory of Computation
Lecture 7:
• More on CFGs
• Pushdown Automata
Reading:
Sipser Ch 2.1-2.3
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/11/2020 CS332 – Theory of Computation 2

Context-Free Grammar
Example Grammar 𝐺 𝑆 →0𝑆1𝐴|1𝑆0𝐴|𝜀
𝐴 →#|𝜀 Derivation
Parse Tree
2/11/2020 CS332 – Theory of Computation
3

Context-Free Languages
𝐿 is a context-free language if it is the language of some CFG
Questions about CFLs
1. Which languages are not context-free?
2. How do we recognize whether 𝑤 ∈ 𝐿?
3. What are the closure properties of CFLs?
2/11/2020
CS332 – Theory of Computation 4

Pumping Lemma for context-free languages
Let 𝐿 be a context-free language.
Then there exists a “pumping length” 𝑝 such that
For every 𝑤 ∈ 𝐿 where |𝑤| ≥ 𝑝,
𝑤 can be split into five parts 𝑤 = 𝑢𝑣𝑥𝑦𝑧 where:
1. |𝑣𝑦| > 0
2. |𝑣𝑥𝑦| ≤ 𝑝
3. 𝑢𝑣𝑖𝑥𝑦𝑖𝑧𝐿forall𝑖 ≥ 0
2/11/2020 CS332 – Theory of Computation 5

Pumping Lemma example
Claim: 𝐿 = 𝑎𝑛𝑏𝑛𝑐𝑛 𝑛 ≥ 0} is not context-free
Proof: Assume 𝐿 is context-free with pumping length 𝑝
1.Find𝑤∈𝐿with 𝑤 ≥𝑝
2. Show that 𝑤 cannot be pumped
If 𝑤 = 𝑢𝑣𝑥𝑦𝑧 with |𝑣𝑦| > 0,|𝑣𝑥𝑦| ≤ 𝑝, then… Case 1: 𝑣, 𝑦 both contain only one kind of symbol Case 2: Either 𝑣 or 𝑦 contains two kinds of symbols
2/11/2020 CS332 – Theory of Computation 6

Pumping Lemma example
Claim: 𝐿 = 𝑎𝑛𝑏𝑛𝑐𝑛 𝑛 ≥ 0} is not context-free
Proof: Assume 𝐿 is context-free with pumping length 𝑝
1.Find𝑤∈𝐿with 𝑤 ≥𝑝
2. Show that 𝑤 cannot be pumped
If 𝑤 = 𝑢𝑣𝑥𝑦𝑧 with |𝑣𝑦| > 0,|𝑣𝑥𝑦| ≤ 𝑝, then… Case 2: Either 𝑣 or 𝑦 contains two kinds of symbols
2/11/2020 CS332 – Theory of Computation 8

Pumping Lemma: Proof idea
Let 𝐿 be a context-free language. If 𝑤 ∈ 𝐿 is long enough, then every parse tree for 𝑤 has a repeated variable.
2/11/2020 CS332 – Theory of Computation 9

Pumping Lemma Proof
What does “long enough” mean? (How do we choose the pumping length 𝑝?)
• Let 𝐺 be a CFG for 𝐿
• Suppose the right-hand side of every rule in 𝐺 uses at
most 𝑏 symbols • Let 𝑝 = 𝑏 𝑉 +1
Claim: If 𝑤 ∈ 𝐿 with 𝑤 ≥ 𝑝, then the smallest parse tree for𝑤hasheightatleast 𝑉 +1
2/11/2020 CS332 – Theory of Computation 10

Pumping Lemma Proof
Claim: If 𝑤 ∈ 𝐿 with 𝑤 ≥ 𝑝, then the smallest parse tree for𝑤hasheightatleast 𝑉 +1
• 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 11

Pushdown Automata
2/11/2020 CS332 – Theory of Computation 13

Regular Expressions : Finite Automata :: Context-Free Languages : ???
2/11/2020 CS332 – Theory of Computation 14

Pushdown Automata
𝑎
𝑏
𝑎
𝑎
Input
… Finite Automata (FAs): Machine with a finite
amount of unstructured memory
Finite control
𝑎
𝑏
𝑎
𝑎
Input
… Pushdown Automata (PDAs): Machine with unbounded structured memory in the
form of a stack
Memory: Infinite Stack
𝑥
𝑥
𝑦
Finite control
2/11/2020
CS332 – Theory of Computation 15

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/11/2020
CS332 – Theory of Computation
16

Example: Even Palindromes
𝐿={𝑤𝑤𝑅|𝑤∈ 0,1∗}
Input
…
𝑎
𝑏
𝑏
𝑏
𝑏
𝑎
Finite control
2/11/2020
CS332 – Theory of Computation 17
Memory: Infinite Stack

Example: Even Palindromes
𝐿={𝑤𝑤𝑅|𝑤∈ 0,1∗}
Input
…
𝑎
𝑏
𝑏
𝑏
𝑏
𝑎
Finite control
Algorithmic Description
1. Place the marker $ on the stack
2. Nondeterministically, either
Memory: Infinite Stack
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/11/2020 CS332 – Theory of Computation 18

Example: Even Palindromes
𝑞0
𝜀,𝜀 → $
𝑝
𝑎,𝜀 → 𝑎
𝑏,𝜀 →𝑏
𝜀,𝜀→ 𝜀
𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀
𝑞𝑓
𝜀,$ → 𝜀
𝑞
2/11/2020
CS332 – Theory of Computation
19

Pushdown Automaton (formal)
A PDA is a 6-tuple (sorry) 𝑀 = (𝑄,Σ,Γ,𝛿,𝑞0,𝐹)
• 𝑄 is a finite set of states
• Σ is the input alphabet
• Γ is the stack alphabet
• 𝛿 : 𝑄 × Σ × Γ → 𝑃(𝑄 × Γ ) is the transition function 𝜀𝜀𝜀
• 𝑞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/11/2020 CS332 – Theory of Computation 20

Example: Even Palindromes
𝑞0
𝜀,𝜀 → $ 𝑎,𝜀 → 𝑎
𝑝 𝑏,𝜀 →𝑏 𝜀,𝜀→ 𝜀
𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀
𝛿:𝑄×Σ×Γ→𝑃𝑄×Γ 𝜀𝜀𝜀
𝛿 𝑝,𝑏,𝜀 = 𝛿 𝑞,𝑎,𝑎 = 𝛿 𝑞,𝑎,𝑏 =
𝑄= Σ= Γ= 𝐹=
𝑞𝑓
𝜀,$ → 𝜀
𝑞
2/12/2020
CS332 – Theory of Computation 21

Example
𝐿 = {𝑤|𝑤 has an equal number of 𝑎’s and 𝑏’s}
2/11/2020 CS332 – Theory of Computation 22

Example
𝐿 = {𝑤|𝑤 has an equal number of 𝑎’s and 𝑏’s}
2/11/2020 CS332 – Theory of Computation 23

CFGs vs. PDAs
The language 𝐿(𝑀) of a PDA 𝑀 is the set of all strings it accepts.
Theorem (next time): The class of languages recognized by PDAs is exactly the context-free languages.
2/11/2020 CS332 – Theory of Computation 24

Closure Properties
• The class of CFLs is closed under the regular operations union, concatenation, star
• Beware: It is not closed under intersection or complement (Find a counterexample!)
2/11/2020 CS332 – Theory of Computation 26

Closure under union (Proof 1)
Let 𝐴 be a CFL recognized by PDA 𝑀 and let 𝐵 be a CFL
𝐴 Goal: Construct a PDA recognizing 𝐴 ∪ 𝐵
recognized by PDA 𝑀 𝐵
2/11/2020 CS332 – Theory of Computation 27

Closure under union (Proof 2)
Let 𝐴 be a CFL generated by CFG 𝐺 and let 𝐵 be a CFL
𝐴
Goal: Construct a CFG 𝐺 recognizing 𝐴 ∪ 𝐵
recognized by CFG 𝐺𝐵 𝐺 =(𝑉,Σ,𝑅,𝑆)
𝐴 𝐴𝐴𝐴𝐴
𝐺 =(𝑉,Σ,𝑅,𝑆) 𝐵 𝐵𝐵𝐵𝐵
Relabel variables so 𝑉 and 𝑉 are disjoint 𝐴𝐵
Let𝐺 =(𝑉,Σ,𝑅,𝑆)
2/12/2020 CS332 – Theory of Computation 28

Related Posts