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