# 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 1: 𝑣, 𝑦 both contain only one kind of symbol

2/11/2020 CS332 – Theory of Computation 7

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

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 12

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

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 25

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