Understanding Decidability and Tractability in CS21 Lecture

CS21
Decidability
and
Tractability
Lecture 9
January 24, 2024
January 24, 2024
CS21 Lecture 9
2
Deciding CFLs
Convert CFG into 
Chomsky Normal Form
parse tree for string 
x
 generated by
nonterminal 
A
:
A
B
C
x
January 24, 2024
CS21 Lecture 9
3
Deciding CFLs
 
An algorithm:
I
s
G
e
n
e
r
a
t
e
d
(
x
,
 
A
)
if |x| = 1, then return YES if A → x is a production,
else return NO
for all n-1 ways of splitting x = yz
    for all ≤ m productions of form A → BC
        if IsGenerated(y, B) and IsGenerated(z, C),
  
return YES
return NO
worst case running time?
January 24, 2024
CS21 Lecture 9
4
Deciding CFLs
January 24, 2024
CS21 Lecture 9
5
Deciding CFLs
January 24, 2024
CS21 Lecture 9
6
Deciding CFLs
O(nm) steps
O(n
3
m
3
) steps
January 24, 2024
CS21 Lecture 9
7
Deterministic PDA
January 24, 2024
CS21 Lecture 9
8
Deterministic PDA
 
A technical detail:
 
we will give our deterministic machine the
ability to detect end of input string
add special symbol ■ to alphabet
require input tape to contain x■
language recognized by a deterministic
PDA is called a 
deterministic CFL
 (DCFL)
January 24, 2024
CS21 Lecture 9
9
Example deterministic PDA
ε
, 
ε
 
 $
, $
 
 
ε
1, 0
 
 
ε
0, 
ε
 
 0
1, 0
 
 
ε
January 24, 2024
CS21 Lecture 9
10
Deterministic PDA
 
T
h
e
o
r
e
m
:
 
D
C
F
L
s
 
a
r
e
 
c
l
o
s
e
d
 
u
n
d
e
r
c
o
m
p
l
e
m
e
n
t
(complement of L in 
Σ
* is (
Σ
* - L) )
Proof attempt:
swap accept/non-accept states
problem: might enter infinite loop before
reading entire string
machine for complement must accept in these
cases, and read to end of string
January 24, 2024
CS21 Lecture 9
11
Example of problem
0, 
ε
 
 
ε
0, 
ε
 
 
ε
1, 
ε
 
 
ε
1, 
ε
 
 
ε
ε
, 
ε
 
 $
, 
ε
 
 
ε
, 
ε
 
 
ε
ε
, 
ε
 
 $
January 24, 2024
CS21 Lecture 9
12
Example of problem
0, 
ε
 
 
ε
0, 
ε
 
 
ε
1, 
ε
 
 
ε
1, 
ε
 
 
ε
ε
, 
ε
 
 $
, 
ε
 
 
ε
, 
ε
 
 
ε
ε
, 
ε
 
 $
January 24, 2024
CS21 Lecture 9
13
Deterministic PDA
Proof:
convert machine into “normal form”
always reads to end of input
always enters either an accept state or single
distinguished “reject” state, and stay there
step 1: keep track of when we have read to
end of input
step 2: eliminate infinite loops
January 24, 2024
CS21 Lecture 9
14
Deterministic PDA
step 1: keep track of when we have read to end
of input
■, ? 
 ?
q
0
q
1
q
3
q
2
 
■, ? 
 ?
 
q
0
 
q
1
 
q
3
 
q
2
January 24, 2024
CS21 Lecture 9
15
Deterministic PDA
step 1: keep track of when we have read to end
of input
■, ? 
 ?
q
0
q
1
q
3
q
2
■, ? 
 ?
q
0
q
1
q
3
q
2
 
for accept state q’: replace outgoing “
ε
, ? → ?”
transition with self-loop with same label
January 24, 2024
CS21 Lecture 9
16
Deterministic PDA
step 2: eliminate infinite loops
add new “reject” states
r’
r
a, t 
t  (for all a, t)
ε
, t 
 t  (for all t)
, t 
 t  (for all t)
January 24, 2024
CS21 Lecture 9
17
Deterministic PDA
step 2: eliminate infinite loops
on input x, if infinite loop, then:
stack
height
time
i
0
i
1
i
2
i
3
infinite
 sequence i
0
< i
1
< i
2
< … such
that for all k, stack height never
decreases below ht(i
k
) after time i
k
January 24, 2024
CS21 Lecture 9
18
Deterministic PDA
step 2: eliminate infinite loops
infinite seq. i
0
< i
1
< … such that for all k, stack
height never decreases below ht(i
k
) after time i
k
infinite subsequence j
0
< j
1
< j
2
< … such that
same transition is applied at each time j
k
p
ε
, t 
 s
 
 never see any stack symbol below
t from j
k
 on
 we are in a periodic, deterministic
sequence of stack operations
independent of the input
CS21 Lecture 9
19
Deterministic PDA
step 2: eliminate infinite loops
infinite subsequence j
0
< j
1
< j
2
< … such that
same transition is applied at each time j
k
safe to replace:
p
 
ε
, t 
 s
r’
r
a, t 
t  (for all a, t)
ε
, t 
 t  (for all t)
, t 
 t  (for all t)
 
p’
 
ε
, t 
 s
 
ε
, t 
 s
or
 
ε
, t 
 s
January 24, 2024
CS21 Lecture 9
20
Deterministic PDA
 
finishing up…
have a machine M with no infinite loops
therefore it always reads to end of input
either enters an accept state q’, or enters
“reject” state r’
 
now, can swap: make r’ unique accept state
to get a machine recognizing complement of L
January 24, 2024
CS21 Lecture 9
21
Summary
Nondeterministic Pushdown Automata
(NPDA)
Context-Free Grammars (CFGs) describe
Context-Free Languages (CFLs)
terminals, non-terminals
productions
yields, derivations
parse trees
January 24, 2024
CS21 Lecture 9
22
Summary
grouping determined by grammar
Chomsky Normal Form (CNF)
NDPAs and CFGs are equivalent
CFL Pumping Lemma is used to show
certain languages are not CFLs
January 24, 2024
CS21 Lecture 9
23
Summary
deterministic PDAs recognize DCFLs
DCFLs are closed under complement
there is an efficient algorithm (based on
dynamic programming) to determine if a
string x is generated by a given grammar G
January 24, 2024
CS21 Lecture 9
24
So far…
several 
models of computation
finite automata
pushdown automata
fail to capture our intuitive notion of what is
computable
 
regular
languages
 
context free
languages
 
all languages
January 24, 2024
CS21 Lecture 9
25
So far…
We proved (using constructions of FA and
NPDAs and the two pumping lemmas):
regular
languages
context free
languages
all languages
 
{a
n
b
n 
: n ≥ 0 }
 
{a
n
b
n
c
n 
: n ≥ 0 }
January 24, 2024
CS21 Lecture 9
A more powerful machine
limitation of NPDA related to fact that their
memory is stack-based (last in, first out)
What is the 
simplest
 alteration that adds
general-purpose “memory” to our
machine?
Should be able to recognize, e.g., 
{a
n
b
n
c
n 
: n 
≥ 0
 }
26
January 24, 2024
CS21 Lecture 9
Turing Machines
 
New capabilities:
infinite tape
can read OR write to tape
read/write head can move left and right
0
1
1
0
0
1
1
1
0
1
0
0
q
0
input tape
finite
control
read/write
head
27
January 24, 2024
CS21 Lecture 9
Turing Machine
 
Informal description:
input written on left-most squares of tape
rest of squares are blank
at each point, take a step determined by
current symbol being read
current state of finite control
a step consists of
writing new symbol
moving read/write head left or right
changing state
28
January 24, 2024
CS21 Lecture 9
Example Turing Machine
0
1
#
0
1
q
0
input tape
finite
control
read/write
head
29
January 24, 2024
CS21 Lecture 9
Turing Machine diagrams
 
a 
→ R means “read a, move right”
a 
→ L means “read a, move left”
a → b, R means “read a, write b, move right
a 
 R
b 
 R
b 
 L
a 
 b,L
b 
 a,R
 
start state
 
transition label: 
(tape symbol read 
tape symbol written, direction moved)
q
accept
q
reject
 
states
(1 accept
+ 1 reject)
 
“_” means
blank tape
square
30
January 24, 2024
CS21 Lecture 9
Example TM diagram
q
accept
q
0
q
1
q
3
q
5
q
7
q
9
q
11
q
12
q
13
q
2
q
4
q
6
q
8
q
10
0 
_
,R
1 
_
,R
# 
R
0,1 
R
0,1 
R
0,1,# 
L
0,1 
R
x 
R
#
R
_
L
_
R
#
R
0,1 
R
0,1 
R
0,1,# 
L
0,1 
R
x 
R
#
R
_
L
_
R
#
R
0 
→ x, 
L
1 
→ x, 
L
0,1,x,# 
L
0 
→ x, 
R
1 
→ x, 
R
x 
R
x 
R
_
R
_
R
#
R
31
Slide Note
Embed
Share

Explore the concepts of decidability and tractability in the CS21 lecture on January 24, 2024. The lecture covers topics such as converting context-free grammars into Chomsky Normal Form, algorithms for determining language generation, worst-case running times, dynamic programming strategies, and deterministic PDAs.


Uploaded on Sep 10, 2024 | 3 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. CS21 Decidability and Tractability Lecture 9 January 24, 2024

  2. Deciding CFLs Convert CFG into Chomsky Normal Form parse tree for string x generated by nonterminal A: If A k x (k > 1) then there must be a way to split x: A B C x = yz A BC is a production and B i y and C j z for i, j < k x January 24, 2024 CS21 Lecture 9 2

  3. Deciding CFLs An algorithm: IsGenerated(x, A) if |x| = 1, then return YES if A x is a production, else return NO for all n-1 ways of splitting x = yz for all m productions of form A BC if IsGenerated(y, B) and IsGenerated(z, C), return YES return NO worst case running time? January 24, 2024 CS21 Lecture 9 3

  4. Deciding CFLs worst case running time exp(n) Idea: avoid recursive calls build table of YES/NO answers to calls to IsGenerated, in order of length of substring example of general algorithmic strategy called dynamic programming notation: x[i,j] = substring of x from i to j table: T(i, j) contains {A: A nonterminal such that A * x[i,j]} January 24, 2024 CS21 Lecture 9 4

  5. Deciding CFLs IsGenerated(x = x1x2x3 xn, G) for i = 1 to n T[i, i] = {A: A xi is a production in G} for k = 1 to n - 1 for i = 1 to n - k for k splittings x[i, i+k] = x[i,i+j]x[i+j+1, i+k] T[i, i+k] = {A: A BC is a production in G and B T[i,i+j] and C T[i+j+1,i+k] } output YES if S T[1, n], else output NO January 24, 2024 CS21 Lecture 9 5

  6. Deciding CFLs IsGenerated(x = x1x2x3 xn, G) for i = 1 to n T[i, i] = {A: A xi is a production in G} for k = 1 to n - 1 for i = 1 to n - k for k splittings x[i, i+k] = x[i,i+j]x[i+j+1, i+k] T[i, i+k] = {A: A BC is a production in G and B T[i,i+j] and C T[i+j+1,i+k] } output YES if S T[1, n], else output NO O(nm) steps O(n3m3) steps January 24, 2024 CS21 Lecture 9 6

  7. Deterministic PDA A NPDA is a 6-tuple (Q, , , , q0, F) where: :Q x ( { }) x ( { }) P (Q x ( { })) is a function called the transition function A deterministic PDA has only one option at every step: for every state q Q, a , and t , exactly 1 element in (q, a, t), or exactly 1 element in (q, , t), and (q, a, t) empty for all a January 24, 2024 CS21 Lecture 9 7

  8. Deterministic PDA A technical detail: we will give our deterministic machine the ability to detect end of input string add special symbol to alphabet require input tape to contain x language recognized by a deterministic PDA is called a deterministic CFL (DCFL) January 24, 2024 CS21 Lecture 9 8

  9. Example deterministic PDA 0, 0 , $ = {0, 1} 1, 0 = {0, 1, $} , $ 1, 0 L = {0n1n : n 0} (unpictured transitions go to a reject state and stay there) January 24, 2024 CS21 Lecture 9 9

  10. Deterministic PDA Theorem: DCFLs are closed under complement (complement of L in * is ( * - L) ) Proof attempt: swap accept/non-accept states problem: might enter infinite loop before reading entire string machine for complement must accept in these cases, and read to end of string January 24, 2024 CS21 Lecture 9 10

  11. Example of problem 1, 0, 0, , , 1, , $ , $ Language of this DPDA is 0 * January 24, 2024 CS21 Lecture 9 11

  12. Example of problem 1, 0, 0, , , 1, , $ , $ Language of this DPDA is {?} January 24, 2024 CS21 Lecture 9 12

  13. Deterministic PDA Proof: convert machine into normal form always reads to end of input always enters either an accept state or single distinguished reject state, and stay there step 1: keep track of when we have read to end of input step 2: eliminate infinite loops January 24, 2024 CS21 Lecture 9 13

  14. Deterministic PDA step 1: keep track of when we have read to end of input q0 q0 q1 q1 , ? ? , ? ? q3 q3 q2 q2 January 24, 2024 CS21 Lecture 9 14

  15. Deterministic PDA step 1: keep track of when we have read to end of input , ? ? q0 q0 q1 q1 , ? ? q3 q3 q2 q2 for accept state q : replace outgoing , ? ? transition with self-loop with same label January 24, 2024 CS21 Lecture 9 15

  16. Deterministic PDA step 2: eliminate infinite loops add new reject states a, t t (for all a, t) , t t (for all t) r r , t t (for all t) January 24, 2024 CS21 Lecture 9 16

  17. Deterministic PDA step 2: eliminate infinite loops on input x, if infinite loop, then: stack height time i0 i1i2 i3 infinite sequence i0< i1< i2< such that for all k, stack height never decreases below ht(ik) after time ik January 24, 2024 CS21 Lecture 9 17

  18. Deterministic PDA step 2: eliminate infinite loops infinite seq. i0< i1< such that for all k, stack height never decreases below ht(ik) after time ik infinite subsequence j0< j1< j2< such that same transition is applied at each time jk never see any stack symbol below t from jk on we are in a periodic, deterministic sequence of stack operations independent of the input p , t s January 24, 2024 CS21 Lecture 9 18

  19. Deterministic PDA step 2: eliminate infinite loops infinite subsequence j0< j1< j2< such that same transition is applied at each time jk safe to replace: a, t t (for all a, t) , t t (for all t) , t s r p r , t s , t s , t t (for all t) or p , t s CS21 Lecture 9 19

  20. Deterministic PDA finishing up have a machine M with no infinite loops therefore it always reads to end of input either enters an accept state q , or enters reject state r now, can swap: make r unique accept state to get a machine recognizing complement of L January 24, 2024 CS21 Lecture 9 20

  21. Summary Nondeterministic Pushdown Automata (NPDA) Context-Free Grammars (CFGs) describe Context-Free Languages (CFLs) terminals, non-terminals productions yields, derivations parse trees January 24, 2024 CS21 Lecture 9 21

  22. Summary grouping determined by grammar Chomsky Normal Form (CNF) NDPAs and CFGs are equivalent CFL Pumping Lemma is used to show certain languages are not CFLs January 24, 2024 CS21 Lecture 9 22

  23. Summary deterministic PDAs recognize DCFLs DCFLs are closed under complement there is an efficient algorithm (based on dynamic programming) to determine if a string x is generated by a given grammar G January 24, 2024 CS21 Lecture 9 23

  24. So far several models of computation finite automata pushdown automata fail to capture our intuitive notion of what is computable all languages regular languages context free languages January 24, 2024 CS21 Lecture 9 24

  25. So far We proved (using constructions of FA and NPDAs and the two pumping lemmas): {anbn : n 0 } {w : w {a,b}* has an even # of b s} regular languages all languages context free languages {anbncn : n 0 } January 24, 2024 CS21 Lecture 9 25

  26. A more powerful machine limitation of NPDA related to fact that their memory is stack-based (last in, first out) What is the simplest alteration that adds general-purpose memory to our machine? Should be able to recognize, e.g., {anbncn : n 0 } January 24, 2024 CS21 Lecture 9 26

  27. Turing Machines input tape 0 1 1 0 0 1 1 1 0 1 0 0 finite control read/write head q0 New capabilities: infinite tape can read OR write to tape read/write head can move left and right January 24, 2024 CS21 Lecture 9 27

  28. Turing Machine Informal description: input written on left-most squares of tape rest of squares are blank at each point, take a step determined by current symbol being read current state of finite control a step consists of writing new symbol moving read/write head left or right changing state January 24, 2024 CS21 Lecture 9 28

  29. Example Turing Machine language L = {w#w : w {0,1}*} input tape 0 1 # 0 1 finite control q0 read/write head January 24, 2024 CS21 Lecture 9 29

  30. Turing Machine diagrams a b,L a R states (1 accept + 1 reject) start state b L b R qreject qaccept b a,R transition label: (tape symbol read tape symbol written, direction moved) _ means blank tape square a R means read a, move right a L means read a, move left a b, R means read a, write b, move right January 24, 2024 CS21 Lecture 9 30

  31. Example TM diagram 0,1 R 0,1 R 0,1,# L 0,1 R x R # R _ L _ R # R q1 q3 q5 q7 q9 0 _,R 0 x, R 0 x, L x R # R x R _ R 0,1,x,# L _ R q0 q11 q12 q13 qaccept # R 1 x, R 1 x, L 1 _,R q2 q4 q6 q8 q10 # R _ L _ R # R 0,1 R 0,1 R 0,1,# L 0,1 R x R January 24, 2024 CS21 Lecture 9 31

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#