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

BU CS 332 – Theory of Computation

Lecture 8:

• Equivalence between PDAs and CFGs

Reading: Sipser Ch 2.2

• Closure Properties

Mark Bun February 18, 2020

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/18/2020

CS332 ‐ Theory of Computation

2

Finite control

𝑥 𝑥 𝑦

𝑎,𝑥 → 𝑥′

Memory: Infinite Stack

Example: Even Palindromes

2/18/2020

CS332 ‐ Theory of Computation

3

𝜀,𝜀 → $ 0

𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏

𝜀,$ → 𝜀 𝑓

𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀

𝜀,𝜀→ 𝜀

Pushdown Automaton (formal)

A PDA is a 6‐tuple

• • •

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/18/2020 CS332 ‐ Theory of Computation 4

Example

has an equal number of ’s and ’s

Algorithmic description

2/18/2020 CS332 ‐ Theory of Computation

5

Example

State diagram

has an equal number of ’s and ’s

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/18/2020 CS332 ‐ Theory of Computation 7

CFG ‐> PDA

2/18/2020 CS332 ‐ Theory of Computation 8

CFG ‐> PDA Conversion

Suppose language is generated by CFG = Goal: Construct a PDA

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/18/2020 CS332 ‐ Theory of Computation 9

Algorithmic Description

1.

Place and the start variable on the stack Repeat forever:

2.

a)

If the top of the stack holds variable : Nondeterministically guess a rule Replace with on the stack

b) c)

If the top of the stack holds terminal :

Pop and verify that it matches the next input char

If the top of the stack holds : Accept if the input is empty

2/18/2020 CS332 ‐ Theory of Computation 10

State Diagram

0 𝜀, 𝜀 → 𝑆$

𝑙𝑜𝑜𝑝 𝜀, $ → 𝜀

𝜀,𝐴 → 𝑢 𝜎,𝜎 → 𝜀

[foreveryrule𝐴 → 𝑢] [for every terminal 𝐴 → 𝜎]

2/18/2020

CS332 ‐ Theory of Computation 11

𝑓

Example

0 𝜀, 𝜀 → 𝑆$

𝑙𝑜𝑜𝑝 𝜀, $ → 𝜀

2/18/2020

CS332 ‐ Theory of Computation 12

𝑓

Example

𝑙𝑜𝑜𝑝 𝜀, $ → 𝜀

2/18/2020

CS332 ‐ Theory of Computation 13

0

𝑓

PDA ‐> CFG

2/18/2020 CS332 ‐ Theory of Computation 14

PDA ‐> CFG Conversion

Theorem 2: Every PDA has an equivalent CFG Suppose is recognized by PDA

Goal: Construct a CFG = First simplify so that:

generating

1. 2. 3.

It has a single accept state

It empties the stack before accepting

Every transition either pushes a symbol or pops a symbol (but not both)

2/18/2020 CS332 ‐ Theory of Computation 15

𝑓

Simplification Example

2/18/2020

CS332 ‐ Theory of Computation 16

𝜀,𝜀 → $ 0

𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏

𝜀,$ → 𝜀 𝑓

𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀

𝜀,𝜀→ 𝜀

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/18/2020 CS332 ‐ Theory of Computation 17

Example 𝜀,𝜀 → $ 0

1

𝑎,𝜀 → 𝑎 𝑏,𝜀 →𝑏

6

5

2

𝜀,# →𝜀

𝜀, 𝜀 → #

𝜀, 𝜀 → #

What strings should 𝐴 generate? What strings should 𝐴 generate?

What strings should 𝐴 generate?

2/18/2020 CS332 ‐ Theory of Computation

18

𝜀, 𝜀 → #

𝜀, # → 𝜀

𝜀,$ → 𝜀 4

3

𝑎,𝑎→ 𝜀 𝑏,𝑏→ 𝜀

What rules should define ?

Let be a string generated by Two cases:

2/18/2020

CS332 ‐ Theory of Computation 19

1) Stack first empties after reading all of stack

input string

𝑝𝑞

height

2) Stack empties before reaching the end of stack

input string

𝑝𝑞

height

1. Stack first empties after reading all of

input string

2/18/2020

CS332 ‐ Theory of Computation

20

stack height

Add rule

2. Stack empties before reaching the end of

input string

2/18/2020

CS332 ‐ Theory of Computation 21

stack height

Add rule

Formal CFG Construction

Three kinds of rules:

1. For every :

If and ,

include the rule 2. For every

3. For every 2/18/2020

include the rule

include the rule

CS332 ‐ Theory of Computation

22

Sketch of proof that CFG generates

Claim: ∗ if and only if takes from to , beginning and ending with empty stack

Proof idea:

Induction on number of steps of derivation of

from

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/18/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/18/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/18/2020 CS332 ‐ Theory of Computation

27