15hjhkllkhhkljbghgfyhgjkhjghfgjgjkghg336479.ppt

ok

1. CSCI 3130: Formal languages and automata theory
Andrej Bogdanov
http://www.cse.cuhk.edu.hk/~andrejb/csc3130
The Chinese University of Hong Kong
Decidable and
undecidable languages
Fall 2010

2. Problems about automata
•We can formulate this question as a language:
q
0 q
1
b
b
a
a
Does accept input abb?
A
DFA= {〈D, w〉: Dis a DFA that accepts input w}
((q0,q1)(a,b)((q0,a,q0)(q0,b,q1)(q1,a,q0)(q1,b,q1)(q0)(q1))(abb)
D= (Q, S, d, q
0, F) w
Is A
DFAdecidable?

3. Problems about automata
A
DFA= {〈D, w〉: Dis a DFA that accepts input w}
pseudocode:
On input 〈D, w〉,
where D= (Q, S, d, q
0, F):
Set q:= q
0
For i := 1 to length(w):
q:= d(q, w
i)
If q F accept, else reject
TM description:
On input 〈D, w〉,
where Dis a DFA, wis a string
SimulateDon input w
If simulation ends in acc state,
accept. Otherwise, reject.

4. Problems about automata
A
DFA= {〈D, w〉: Dis a DFA that accepts input w}
Turing Machine details:
Check input is in correct format.
(Transition function is complete, no duplicate transitions)
Perform simulation:
((q0,q1)(a,b)((q0,a,q0)(q0,b,q1)(q1,a,q0)(q1,b,q1)(q0)(q1))(abb)
. .
state input symbol
... .
q
acc

5. Problems about automata
A
DFA= {〈D, w〉: Dis a DFA that accepts input w}
Turing Machine details:
Check input is in correct format.
(Transition function is complete, no duplicate transitions)
Perform simulation:
Put markers on start state of Dand first symol of w
Until wmarker reaches last symbol:
Update both markers
If state marker is on accepting state, accept. Else reject.

6. Acceptance problems about automata
A
DFA= {〈D, w〉: Dis a DFA that accepts input w}
A
NFA= {〈N, w〉: Nis an NFA that accepts w}
A
REX= {〈R, w〉: Ris a regular expression that generates w}
Which of these is decidable?

7. Acceptance problems about automata
•The following TM decides A
DFA:
A
DFA= {〈D, w〉: Dis a DFA that accepts input w}
M:=On input 〈D, w〉, where Dis a DFA and wis a string
Simulate Don input w
If the simulation ends in acc state of D, accept.
If it doesn’t, reject.

8. Acceptance problems about automata
•The following TM decides A
NFA:
A
NFA= {〈N, w〉: Nis an NFA that accepts input w}
N:=On input 〈N, w〉, where Nis an NFA and wis a string
Convert Nto a DFA D
using the conversion procedure from Lecture
2
Run the TM Mfor A
DFAon input 〈D, w〉
If Maccepts, accept. Otherwise, reject.

9. Acceptance problems about automata
•The following TM decides A
REX:
A
REX= {Ris a regular expression that generates w}
P:=On input 〈R, w〉, where Ris a reg exp and wis a string
Convert Rto an NFA A
using the conversion procedure from Lecture
4
Run the TM Nfor A
NFAon input 〈A, w〉
If Naccepts, accept. Otherwise, reject.

10. Other problems about automata
MIN
DFA= {〈D〉: Dis a minimal DFA}
On input 〈D〉, where Dis a DFAR:=
Run the distinguishable states
algorithm
from Lecture 7 on D
If every pair of states is distinguishable,
accept.Otherwise, reject.
•The following TM decides MIN
DFA:

11. Other problems about automata
EQ
DFA= {〈D
1, D
2〉: D
1, D
2are DFAs and L(D
1) = L(D
2)}
On input 〈D
1, D
2〉, where D
1and D
2are DFAsS:=
Run the DFA minimization algorithm
from Lecture 7 on D
1to obtain a DFA D
1’
•The following TM decides EQ
DFA:
If D
1 = D
2accept, otherwise reject.
Run the DFA minimization algorithm
from Lecture 7 on D
2to obtain a DFA D
2’

12. Other problems about automata
E
DFA= {〈D〉: D is a DFAs and L(D)is empty}
On input 〈D〉, where Dis a DFAT:=
Run the TM Sfor EQ
DFAon input 〈D,〉
•The following TM decides E
DFA:
If Saccepts accept, otherwise reject.

13. Problems about context-free grammars
A
CFG= {〈G, w〉: Gis a CFG that generates w}
On input 〈G,w〉, where Gis a CFG and wis a stringV:=
If the CYK algorithm produces a parse tree,
accept.
Eliminate the nullable and unit productions from G
Convert Gto Chomsky Normal Form
Run the Cocke-Younger-Kasami algorithm on 〈
G,w〉
Otherwise, reject.

14. Decidability of context-free languages
Every context-free language is decidable.
Let Lbe a context-free language.
There is a CFG Gfor L.
The following TM decides L:
M
G:=On input w,
Run TM Von input 〈G,
w〉.
If Vacceptsaccept, otherwise reject.

15. Are all languages about CFGs
decidable?
EQ
CFG= {〈G
1,G
2〉: G
1andG
2are context-free grammars
that generate the same strings}
What’s the difference between EQ
DFAand EQ
CFG?
To decide EQ
DFA, we minimized both DFAs
But there is no method that, given a CFG or PDA,
produces a unique equivalent minimal CFG or PDA

16. The universal Turing Machine
and undecidability

17. Turing Machines versus computers
computer
input
program
output
A computeris a machine that manipulates data
according to a list of instructions.
How does a Turing Machine take a program
as part of its input?

18. The Universal Turing Machine
U
input x
program 〈M
〉 Mon input x
The universal TMUtakes as inputs a program M
and a string xand simulates Mon x
The program Mitself is specified as a TM!

19. Turing Machines as strings
•This Turing Machine can be described by the
string
〈M〉=(q,qa,qr)(0,1)(0,1,☐)
((q,q,☐/☐R)
(q,qa,0/0R)
(q,qr,1/1R))
(q)(qa)(qr)
M
q
q
a
q
r
☐/☐R
A Turing Machine is
(Q, S,, d, q
0, q
acc,
q
rej)

20. The universal Turing Machine
U
(q,qa,qr)(0,1)(0,1, 001
input wfor Mprogram 〈M
〉
U:=On input 〈M, w〉,
SimulateMon input w
If Menters accept state, accept.
If Menters reject state, reject.

21. Acceptance of Turing Machines
A
TM= {〈M, w〉: Mis a TM that accepts w}
U:=On input 〈M, w〉,
SimulateMon input w
Maccepts w Mrejects w Mloops on w
Uaccepts 〈M, w〉Urejects 〈M, w〉Uloops on 〈M, w〉
TM Urecognizesbut does not decideA
TM

22. Recognizing versus deciding
The language recognized by a TM is the
set of
all inputs that make it accept
A TM decides language Lif it recognizes L
and
halts (does not loop) on every input
q
acc q
rej
accept reject loop
halt

23. Undecidability
•Turing’s Theorem:
•Before we show this, let’s observe one thing:
The language A
TMis undecidable.
A Turing Machine Mcan be given its own
description〈M〉as an input!

24. Turing’s theorem
A TM that
decides A
TMis so
potent that it will
destroy itself.

25. Proof of Turing’s Theorem
•Proof by contradiction:
Suppose A
TMis decidable.
Then there is a TM Hthat decides A
TM:
H
〈M,w〉 acceptifMaccepts w
rejectifMrejects w
or Mloops on
w
〈M,〈M〉〉 acceptifMaccepts 〈M〉
rejectifMrejects 〈M〉
or Mloops on 〈M〉
What happens whenw= 〈M〉?

26. Proof of undecidability
H
〈M,〈M〉〉 acceptifMaccepts 〈M〉
rejectifMrejects 〈M〉
or Mloops on 〈M〉
Let H’be a TM that does the oppositeof H
H
acc
rej
acc
rej
H’
H= (Q, S,, d, q
0, q
acc, q
rej)
H’= (Q, S,, d, q
0, q
rej, q
acc)

27. Proof of undecidability
H
〈M,〈M〉〉 acceptifMaccepts 〈M〉
rejectifMrejects 〈M〉
or Mloops on 〈M〉
H’
〈M,〈M〉
〉
rejectifMaccepts 〈M〉
ifMrejects 〈M〉
or Mloops on 〈M〉
accept

28. Proof of undecidability
H’
〈M,〈M〉〉
rejectifMaccepts 〈M〉
ifMrejects 〈M〉
or Mloops on 〈M〉
accept
Let Dbe the following TM:
copy
〈M〉 〈M,〈M〉〉
H’

29. Proof of undecidability
D
〈M〉
rejectifMaccepts 〈M〉
ifMrejects 〈M〉
or Mloops on 〈M〉
accept
What happens when M= D?
〈D
〉
rejectifDaccepts 〈D〉
ifDrejects 〈D〉
or Dloops on 〈D〉
If Daccepts 〈D〉then Drejects 〈D〉
If Drejects 〈D〉then Daccepts 〈D〉
so Ddoes not exist!
Hnever loops, so H’
and Dnever loop either

30. Proof of undecidability: conclusion
•Proof by contradiction
–We assumed A
TMwas decidable
–Then we had Turing Machines H, H’, D
–But Ddoes not exist!
•Conclusion
The language A
TMis undecidable.

31. What happened?
M
1
M
2
M
3
…
e 0 1 00…
accrej rej acc
rejacclooprej
rejlooprejrej
…
…
Turing Machines
all possible inputs w
We can write an infinite table for every pair (M, w)
all possible

32. What happened?
M
1
M
2
M
3
…
〈M
1〉〈M
2〉 〈M
4〉…
acclooprej acc
rejacc rejacc
looprejlooprej
…
…
Now let’s look only at those wthat describe a TM M
〈M
3〉

33. What happened?
M
1
M
2
…
〈M
1〉〈M
2〉 〈M
4〉…
acclooprej acc
rejacc rejacc…
…
If A
TMis decidable, then TM Dis in the table
〈M
3〉
Drejrejacc rej
… …

34. What happened?
M
1
M
2
…
〈M
1〉〈M
2〉 〈M
4〉…
acclooprej acc
rejacc rejacc…
…
Ddoes the opposite of the diagonal entries
〈M
3〉
Drejrejacc rej
D
〈M〉
reject ifMaccepts 〈M〉
accept ifMrejects or loops on 〈M〉

35. What happened?
M
1
M
2
…
〈M
1〉〈M
2〉 〈M
4〉…
acclooprejacc
rejacc rejacc…
…
We run into trouble when we look at (D, 〈D〉)!
〈M
3〉
Drejrejacc rej
〈D〉
loop
acc
?…

36. Unrecognizable languages
•How about languages that are not recognizable?
The language A
TMis recognizable but not
decidable.
A
TM= {〈M, w〉: Mis a TM that does not accept w}
= {〈M, w〉: Mrejects or loops on input w}
The language A
TMis not recognizable.

37. Unrecognizable languages
•Theorem
•We know A
TMis recognizable, so if A
TMwere
also,
then A
TMwould be decidable
•Impossible by Turing’s Theorem
If Land Lare both recognizable, then Lis
decidable.

38. Unrecognizable languages
•Proof idea
If Land Lare both recognizable, then Lis
decidable.
M rej/loop ifw∉L
accept ifw∈L
w
M’rej/loop ifw∈L
accept ifw∉L
w
w
accept
reject

39. Unrecognizable languages
Let M= TM for L, M’= TM for L
On input w,
Simulate Mon input w. If it accepts, accept.
Simulate M’on input w. If it accepts, reject.
If Land Lare both recognizable, then Lis
decidable.
Problem: If Mloops on w, we
will never get to step 2!
①
②

40. Bounded simulation
•Decider for L:
Let M= TM for L, M’= TM for L
On input w,
Simulate Mon input w for ksteps. If it accepts, accept.
Simulate M’on input w for ksteps. If it accepts, reject.
If Land Lare both recognizable, then Lis
decidable.
For k= 0 to infinity