CS21 Decidability and Tractability
Lecture 8 January 22, 2024
NPDA, CFG equivalence Theorem: a language L is recognized by a
NPDA iff L is described by a CFG.
Copyright By PowCoder代写 加微信 powcoder
Must prove two directions:
(⇒) L is recognized by a NPDA implies L is
described by a CFG.
(⇐) L is described by a CFG implies L is
recognized by a NPDA.
January 22, 2024 CS21 Lecture 8 2
NPDA, CFG equivalence
Proof of (⇐): L is described by a CFG implies L is recognized by a NPDA.
0#1 0#1 0#1
q1 q2 q3 idea:
January 22, 2024
000 A## 1 1 1 $$$
CS21 Lecture 8 3
NPDA, CFG equivalence
1. we’dliketonon-deterministicallyguessthe derivation, forming it on the stack
2. thenscantheinput,poppingmatching symbol off the stack at each step
3. acceptifwegettothebottomofthestackat the end of the input.
what is wrong with this approach?
January 22, 2024 CS21 Lecture 8 4
NPDA, CFG equivalence
– only have access to top of stack – combine steps 1 and 2:
• allow to match stack terminals with tape during the process of producing the derivation on the stack
0#1 0#1 0#1
q3 A→0A1 A 1
January 22, 2024
CS21 Lecture 8 5
NPDA, CFG equivalence
• informal description of construction: – place $ and start symbol S on the stack – repeat:
• if the top of the stack is a non-terminal A, pick a production with A on the lhs and substitute the rhs for A on the stack
• if the top of the stack is a terminal b, read b from the tape, and pop b from the stack.
• if the top of the stack is $, enter the accept state. January 22, 2024 CS21 Lecture 8 6
NPDA, CFG equivalence
ε, ε → S$ ε,A→w
one transition for
each production
q ε, A → w = w1
January 22, 2024
one transition for
shorthand for: ε, ε → wk-1
ε, A → wk q2
each terminal b
CS21 Lecture 8
NPDA, CFG equivalence Proof of (⇒): L is recognized by a NPDA
implies L is described by a CFG.
– harder direction
– first step: convert NPDA into “normal form”:
• single accept state
• empties stack before accepting
• each transition either pushes or pops a symbol
January 22, 2024 CS21 Lecture 8 8
NPDA, CFG equivalence
– main idea: non-terminal Ap,q generates exactly the strings that take the NPDA from state p (w/ empty stack) to state q (w/ empty stack)
– then Astart, accept generates all of the strings in the language recognized by the NPDA.
January 22, 2024 CS21 Lecture 8 9
NPDA, CFG equivalence
• Two possibilities to get from state p to q:
stack height
January 22, 2024
generated by Ap,r
generated by Ar,q prq
abcabbacacbacbacabacabbabbabaacabbbababaacaccaccccc
string taking NPDA from p to q
CS21 Lecture 8 10
NPDA, CFG equivalence
• NPDA P = (Q, Σ, Γ, δ, start, {accept}) • CFG G:
– non-terminals V = {Ap,q : p, q ∈ Q} – start variable Astart, accept
– productions:
for every p, r, q ∈Q, add the rule Ap,q → Ap,rAr,q
January 22, 2024 CS21 Lecture 8 11
NPDA, CFG equivalence
• Two possibilities to get from state p to q:
stack height
January 22, 2024
generated by Ar,s
p push d pop d q
abcabbacacbacbacabacabbabbabaacabbbababaacaccaccccc
string taking NPDA from p to q
CS21 Lecture 8 12
NPDA, CFG equivalence
• CFG G: move to state r – non-terminals V = {Ap,q f:ropm, qs∈taQte}s,
– start variable Astart, acceprtead b, pop d,
• NPDA P = (Q, Σ, Γ, δ, start, {accept}) read a, push d,
from state p,
– productions:
move to state q
for every p, r, s, q ∈ Q, d ∈ Γ and a, b ∈ (Σ ∪ {ε}) if (r,d)∈δ(p,a,ε),and
(q, ε) ∈ δ(s, b, d), add the rule Ap,q → aAr,sb
January 22, 2024 CS21 Lecture 8 13
NPDA, CFG equivalence
• NPDA P = (Q, Σ, Γ, δ, start, {accept}) • CFG G:
– non-terminals V = {Ap,q : p, q ∈ Q} – start variable Astart, accept
– productions:
for every p ∈ Q, add the rule Ap,p → ε
January 22, 2024 CS21 Lecture 8 14
NPDA, CFG equivalence • two claims to verify correctness:
1. if Ap,q generates string x, then x can take NPDA P from state p (w/ empty stack) to q (w/ empty stack)
2. ifxcantakeNPDAPfromstatep(w/ empty stack) to q (w/ empty stack), then Ap,q generates string x
January 22, 2024 CS21 Lecture 8 15
NPDA, CFG equivalence
1. if Ap,q generates string x, then x can take NPDA P from state p (w/ empty stack) to q (w/ empty stack)
– induction on length of derivation of x.
– base case: 1 step derivation. must have only terminals on rhs. In G, must be production of form Ap,p → ε.
January 22, 2024 CS21 Lecture 8 16
NPDA, CFG equivalence
1. if Ap,q generates string x, then x can take NPDA P from state p (w/ empty stack) to q (w/ empty stack)
– assume true for derivations of length at most k, prove for length k+1.
– verify case: Ap,q → Ap,rAr,q →k x = yz
– verify case: Ap,q → aAr,sb →k x = ayb
January 22, 2024 CS21 Lecture 8 17
NPDA, CFG equivalence
2. if x can take NPDA P from state p (w/ empty stack) to q (w/ empty stack), then Ap,q generates string x
– induction on # of steps in P’s computation
– base case: 0 steps. starts and ends at same state p. only has time to read empty string ε.
– G contains Ap,p → ε.
January 22, 2024 CS21 Lecture 8 18
NPDA, CFG equivalence
2. if x can take NPDA P from state p (w/ empty stack) to q (w/ empty stack), then Ap,q generates string x
– induction step. assume true for computations of length at most k, prove for length k+1.
– if stack becomes empty sometime in the
middle of the computation (at state r)
• y is read going from state p to r
• z is read going from state r to q
• conclude: Ap,q → Ap,rAr,q →* yz = x
January 22, 2024 CS21 Lecture 8
(Ap,r→* y) (Ar,q→* z)
NPDA, CFG equivalence
2. if x can take NPDA P from state p (w/ empty stack) to q (w/ empty stack), then Ap,q generates string x
– if stack becomes empty only at beginning and end of computation.
• first step: state p to r, read a, push d • go from state r to s, read string y
• last step: state s to q, read b, pop d • conclude: Ap,q → aAr,sb →* ayb = x
January 22, 2024 CS21 Lecture 8
(Ar,s→* y)
NPDA, CFG equivalence
2. if x can take NPDA P from state p (w/ empty stack) to q (w/ empty stack), then Ap,q generates string x
– if stack becomes empty only at beginning and end of computation.
• first step: state p to r, read a, push d • go from state r to s, read string y
• last step: state s to q, read b, pop d • conclude: Ap,q → aAr,sb →* ayb = x
January 22, 2024 CS21 Lecture 8
(Ar,s→* y)
Chomsky Normal Form
• Useful to deal only with CFGs in a simple
normal form
• Most common: Chomsky Normal Form (CNF)
• Definition: every production has form A → BC or S → ε or
where A, B, C are any non-terminals (and
B, C are not S) and a is any terminal.
January 22, 2024 CS21 Lecture 8 22
Chomsky Normal Form
Theorem: Every CFL is generated by a CFG in Chomsky Normal Form.
Proof: exercise or in book…
January 22, 2024 CS21 Lecture 8 23
Deciding CFLs
• Useful to have an efficient algorithm to decide whether string x is in given CFL
– e.g. programming language often described by CFG. Determine if string is valid program.
• If CFL recognized by deterministic PDA, just simulate the PDA.
– but not all CFLs are (homework)…
• Can simulate NPDA, but this takes exponential time in the worst case.
January 22, 2024 CS21 Lecture 8 24
Deciding CFLs
• Convert CFG into Chomsky Normal Form • parse tree for string x generated by
nonterminal A:
IfA→k x (k>1)thentheremust be a way to split x:
January 22, 2024
• A → BC is a production and •B→i yandC⇒j zfori,j