Languages and Finite Automata

Decidable Languages
Fall 2006
Costas Busch - RPI
1
Recall that:
A language L is Turing-Acceptable
if there is a Turing machine M
that accepts L
Also known as: Turing-Recognizable
or
Recursively-enumerable
languages
Fall 2006
Costas Busch - RPI
2
For any string
w :
w L
M halts in an accept state
w L
M halts in a non-accept state
or loops forever
Fall 2006
Costas Busch - RPI
3
Definition:
A language L is decidable
if there is a Turing machine (decider)
which accepts L
and halts on every input string
M
Also known as recursive languages
Fall 2006
Costas Busch - RPI
4
For any string
w:
w L
M halts in an accept state
w L
M halts in a non-accept state
Every decidable language is Turing-Acceptable
Fall 2006
Costas Busch - RPI
5
Sometimes, it is convenient to have Turing
machines with single accept and reject states
qaccept
qreject
These are the only halting states
That result to possible
halting configurations
Fall 2006
Costas Busch - RPI
6
We can convert any Turing machine to
have single accept and reject states
New machine
Old machine
qaccept
x  x ,R
x  x ,R
x  x,L
x  x ,R
Multiple
accept states
Fall 2006
For each tape symbol
x
One accept state
Costas Busch - RPI
7
Do the following for each possible
halting state:
New machine
Old machine
qi x  x, R
For each
qi
Multiple
reject states
Fall 2006
qreject
For all tape symbols x
not used for read in the
other transitions of qi
One reject state
Costas Busch - RPI
8
For a decidable language
Decider for
L:
L
qaccept
Input
string
qreject
Decision
On Halt:
Accept
Reject
For each input string, the computation
halts in the accept or reject state
Fall 2006
Costas Busch - RPI
9
For a Turing-Acceptable language
Turing Machine for
L:
L
qaccept
Input
string
qreject
It is possible that for some input string
the machine enters an infinite loop
Fall 2006
Costas Busch - RPI
10
Problem:
Is number x prime?
Corresponding language:
PRIMES  {1, 2, 3, 5, 7, }
We will show it is decidable
Fall 2006
Costas Busch - RPI
11
Decider for PRIMES :
On input number x :
Divide x with all possible numbers
between 2 and x
If any of them divides x
Then reject
Else accept
Fall 2006
Costas Busch - RPI
12
the decider for the language
solves the corresponding problem
Decider for PRIMES
qaccept
Input number x
(Input string)
is
x
prime?
qreject
Fall 2006
Costas Busch - RPI
YES
(Accept)
NO
(Reject)
13
Theorem:
If a language L is decidable,
then its complement L is decidable too
Proof:
Build a Turing machine M  that
accepts L and halts on every input string
( M  is decider for
Fall 2006
Costas Busch - RPI
L
)
14
Transform accept state to reject
and vice-versa
M
M
qaccept

qreject
qreject
qr

qaccept
qr
qa
qa
Fall 2006
Costas Busch - RPI
15
Turing Machine
On each input string
w
M
do:
1. Let M be the decider for L
2. Run
M
If
If
with input string
w
M accepts then reject
M rejects then accept
Accepts L and halts on every input string
Fall 2006
Costas Busch - RPI
END OF PROOF
16
Undecidable Languages
An undecidable language has no decider:
each Turing machine that accepts L
does not halt on some input string
We will show that:
There is a language which is
Turing-Acceptable and undecidable
Fall 2006
Costas Busch - RPI
17
We will prove that there is a language
L:
•
is not Turing-acceptable
(not accepted by any Turing Machine)
•
L
L
is Turing-acceptable
the complement of a
decidable language is decidable
Therefore,
Fall 2006
L
is undecidable
Costas Busch - RPI
18
Non Turing-Acceptable
Turing-Acceptable
L
L
Decidable
Fall 2006
Costas Busch - RPI
19
A Language which
is not
Turing Acceptable
Fall 2006
Costas Busch - RPI
20
Consider alphabet
Strings of
{a}
{a } :

a, aa, aaa, aaaa, 
1
a a
Fall 2006
2
a
3
Costas Busch - RPI
a
4

21
Consider Turing Machines
that accept languages over alphabet
{a}
They are countable:
M1, M 2 , M 3 , M 4 , 
(There is an enumerator that generates them)
Fall 2006
Costas Busch - RPI
22
Each machine accepts some language over
{a}
M1, M 2 , M 3 , M 4 , 
L( M1), L( M 2 ), L( M 3 ), L( M 4 ), 
Note that it is possible to have
L( M i )  L( M j )
for
i j
Since, a language could be accepted by more than one
Turing machine
Fall 2006
Costas Busch - RPI
23
Example language accepted by M i
L(M i )  {aa, aaaa, aaaaaa}
L( M i )  {a , a , a }
2
4
6
Binary representation
1
2
a
a
L( M i ) 0
1
Fall 2006
a
3
0
4
a
1
0
a
Costas Busch - RPI
5
a
6
1
a
7
0


24
Example of binary representations
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

Fall 2006
Costas Busch - RPI
3
a
4

25
Consider the language
L  {a : a  L( M i )}
i
i
L consists of the 1’s in the diagonal
Fall 2006
Costas Busch - RPI
26
1
2
3
4

a
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

a
a
L  {a , a ,}
3
Fall 2006
4
Costas Busch - RPI
27
Consider the language
L
L  {a : a  L( M i )}
i
i
L  {a : a  L( M i )}
i
L
Fall 2006
i
consists of the 0’s in the diagonal
Costas Busch - RPI
28
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

L  {a , a ,}
1
Fall 2006
2
Costas Busch - RPI
29
Theorem:
Language
L
is not Turing-Acceptable
Proof:
Assume for contradiction that
L
is Turing-Acceptable
There must exist some machine
that accepts L :
L( M k )  L
Fall 2006
Costas Busch - RPI
Mk
30
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

Question: M k  M1 ?
Fall 2006
Costas Busch - RPI
3
a
4

L( M k )  L
31
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

1
Answer:
Fall 2006
a  L( M k )
M k  M1
1
Costas Busch - RPI
a  L ( M1 )
32
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

Question: M k  M 2 ?
Fall 2006
Costas Busch - RPI
3
a
4

L( M k )  L
33
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

2
Answer:
Fall 2006
a  L( M k )
Mk  M2
2
Costas Busch - RPI
a  L( M 2 )
34
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

Question: M k  M 3 ?
Fall 2006
Costas Busch - RPI
3
a
4

L( M k )  L
35
1
a
a
2
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

3
a
4

3
Answer:
Fall 2006
a  L( M k )
M k  M3
3
Costas Busch - RPI
a  L( M 3 )
36
Similarly:
M k  Mi
Because either:
i
a  L( M k )
i
a  L( M i )
the machine
L
Fall 2006
for any
i
a  L( M k )
i
or
Mk
a  L( M i )
i
cannot exist
is not Turing-Acceptable
Costas Busch - RPI
End of Proof
37
Non Turing-Acceptable
L
Turing-Acceptable
Decidable
Fall 2006
Costas Busch - RPI
38
A Language which is
Turing-Acceptable
and Undecidable
Fall 2006
Costas Busch - RPI
39
We will prove that the language
i
i
L  {a : a  L( M i )}
Is TuringAcceptable
There is a
Turing machine
that accepts L
Fall 2006
Undecidable
Each machine
that accepts L
doesn’t halt
on some input string
Costas Busch - RPI
40
1
2
3
4

a
a
L ( M1 )
0
1
0
1

L( M 2 )
1
0
0
1

L( M 3 )
0
1
1
1

L( M 4 )
0
0
0
1

a
a
L  {a , a ,}
3
Fall 2006
4
Costas Busch - RPI
41
Theorem:
The language
i
i
L  {a : a  L( M i )}
Is Turing-Acceptable
Proof: We will give a Turing Machine that
accepts L
Fall 2006
Costas Busch - RPI
42
Turing Machine that accepts
For any input string
L
w
• Compute i , for which
• Find Turing machine
wa
i
Mi
(using the enumerator for Turing Machines)
• Simulate
• If
Mi
Mi
on input
a
i
accepts, then accept
w
End of Proof
Fall 2006
Costas Busch - RPI
43
Observation:
Turing-Acceptable
i
i
L  {a : a  L( M i )}
Not Turing-acceptable
i
i
L  {a : a  L( M i )}
(Thus,
Fall 2006
L
is undecidable)
Costas Busch - RPI
44
Non Turing-Acceptable
Turing-Acceptable
L
L
Decidable
L?
Fall 2006
Costas Busch - RPI
45
Theorem:
L  {a : a  L( M i )}
i
i
is undecidable
Proof:
If
L is decidable
the complement of a
decidable language is decidable
Then
L
is decidable
However, L is not Turing-Acceptable!
Contradiction!!!!
Fall 2006
Costas Busch - RPI
46
Not Turing-Acceptable
Turing-Acceptable
L
L
Decidable
Fall 2006
Costas Busch - RPI
47
Turing acceptable languages
and
Enumerators
Fall 2006
Costas Busch - RPI
48
We will prove:
(weak result)
• If a language is decidable then
there is an enumerator for it
(strong result)
• A language is Turing-acceptable
if and only if
there is an enumerator for it
Fall 2006
Costas Busch - RPI
49
Theorem:
if a language L is decidable then
there is an enumerator for it
Proof:
Let
M be the decider for L
Use
M to build the enumerator for L
Fall 2006
Costas Busch - RPI
50
~
Let M be an enumerator that prints
all strings from input alphabet in proper order
Example:
alphabet is
Fall 2006
{a, b}
a
b
aa
ab
ba (proper order)
bb
aaa
aab
......
Costas Busch - RPI
51
Enumerator for
Repeat:
L
~
1. M generates a string w
2.
M checks if w L
YES: print
NO:
ignore
w to output
w
This part terminates,
because L is decidable
Fall 2006
Costas Busch - RPI
52
Enumerator for L
~
M
Enumerates all
strings of
input alphabet
Give me
next string
string
wi
M
If M accepts wi
then print wi to
output
output
All strings
of
Generates all
Strings in alphabet
Fall 2006
Tests each string
if it is accepted by
Costas Busch - RPI
L
M
53
Example:
L  {b, ab, bb, aaa,....}
~
M
w1
w2
w3
Fall 2006
a
b
aa
ab
ba
bb
aaa
aab
M
Enumeration
Output
reject
accept
reject
b
accept
ab
reject
accept
accept
bb
aaa
reject
Costas Busch - RPI
END OF PROOF
54
Theorem:
if language L is Turing-Acceptable then
there is an enumerator for it
Proof:
Let
M be the Turing machine that accepts L
Use
M to build the enumerator for L
Fall 2006
Costas Busch - RPI
55
Enumerator for
L
~
M
M
Enumerates all
strings of input alphabet
in proper order
Fall 2006
Costas Busch - RPI
Accepts L
56
NAIVE APPROACH
Enumerator for
Repeat:
L
~ generates a string w
M
M checks if w L
YES: print
NO:
ignore
Problem: If w L
machine M
Fall 2006
Costas Busch - RPI
w to output
w
may loop forever
57
BETTER APPROACH
~ Generates first string w
M
1
M executes first step on w1
~ Generates second string w
M
2
M executes first step on w2
second step on
Fall 2006
Costas Busch - RPI
w1
58
~ Generates third string w
M
3
M executes first step on w3
second step on
w2
third step on
w1
And so on............
Fall 2006
Costas Busch - RPI
59
String:
Step in
computation
of string
Fall 2006
w1
w2
w3
w4
1
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
Costas Busch - RPI

60
If for any string wi
machine M halts in an accepting state
then print wi on the output
End of Proof
Fall 2006
Costas Busch - RPI
61
Theorem:
If for language L
there is an enumerator
then L is Turing-Acceptable
Proof:
Using the enumerator for L
we will build a Turing machine
that accepts L
Fall 2006
Costas Busch - RPI
62
Input Tape
w
Turing Machine that accepts
Enumerator
for L
Fall 2006
w
wi
Give me the
next string
in the
enumeration
sequence
L
Compare
If same,
Accept and Halt
Costas Busch - RPI
63
Turing machine that accepts
For any input string
L
w
Loop:
• Using the enumerator of L ,
generate the next string of
L
• Compare generated string with
w
If same, accept and exit loop
End of Proof
Fall 2006
Costas Busch - RPI
64
By combining the last two theorems,
we have proven:
A language is Turing-Acceptable
if and only if
there is an enumerator for it
Fall 2006
Costas Busch - RPI
65

Download Report