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

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

𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏

𝜀,$ → 𝜀 𝑓

𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀

𝜀,𝜀→ 𝜀

𝛿 : 𝑄 Σ Γ → 𝑃 𝑄 Γ

𝛿 𝑝,𝑏,𝜀 𝛿 𝑞,𝑎,𝑎 𝛿 𝑞,𝑎,𝑏