CS计算机代考程序代写 Slide 1

Slide 1

Decidable and Semidecidable Languages
Chapter 20

D and SD Languages
SD

D

Context-Free
Languages

Regular
Languages

Every CF Language is in D
Theorem: The set of context-free languages is a proper subset of D.

Proof:
● Every context-free language is decidable, so the context-free languages are a subset of D.
● There is at least one language, AnBnCn, that is decidable
but not context-free.

So the context-free languages are a proper subset of D.

Decidable and Semidecidable Languages
Almost every obvious language that is in SD is also in D:

AnBnCn = {anbncn, n ≥ 0}
{wcw, w  {a, b}*}
{ww, w  {a, b}*}
{w = xy=z: x,y,z  {0, 1}* and, when x, y, and z are viewed as binary numbers, xy = z}

But there are languages that are in SD but not in D:

H = { : M halts on input w}

D and SD
D is a subset of SD. In other words, every decidable language is also semidecidable.
There exists at least one language that is in SD/D, the donut in the picture.
There exist languages that are not in SD. In other words, the gray area of the figure is not empty.

Subset Relationships between D and SD
 1. There exists at least one SD language that is not D.
2. Every language that is in D is also in SD: If L is in D, then there is a Turing machine M that decides it (by definition).

But M also semidecides it.

Languages That Are Not in SD
Theorem: 3. There are languages that are not in SD.

Proof: Assume any nonempty alphabet .

There is a countably infinite number of SD languages over .

There is an uncountably infinite number of languages over .

So there are more languages than there are languages in SD. Thus there must exist at least one language that is in SD.

Closure of D Under Complement
Theorem: The set D is closed under complement.

Proof: (by construction) If L is in D, then there is a deterministic Turing machine M that decides it.

M:

y n

From M, we construct M to decide L:

Closure of D Under Complement

Proof: (by construction)

M: M’:

This works because, by definition, M is:
deterministic
complete

Since M’ decides L, L is in D.

n
y
y
n

SD is Not Closed Under Complement
Can we use the same technique?

M: M’:

y

Suppose we had:

ML: ML:

Then we could decide L. How?

So every language in SD would also be in D.

But we know that there is at least one language (H) that is in SD but not in D. Contradiction.
SD is Not Closed Under Complement

D and SD Languages
Theorem: A language is in D iff both the language and its complement are in SD.

Proof:

1. L in D implies L and L are in SD:
L is in SD because D  SD.
D is closed under complement
So L is also in D and thus in SD.

2. L and L are in SD implies L is in D:
M1 semidecides L.
M2 semidecides L.
To decide L:
Run M1 and M2 in parallel on w.
Exactly one of them will eventually accept.

Theorem: The language H =

{ : TM M does not halt on input string w}

is not in SD.

Proof:
H is in SD.
If H were also in SD then H would be in D.
But H is not in D.
So H is not in SD.

A Language that is Not in SD

Enumerate means list. We look at Turing Machines as generators.

We say that Turing machine M enumerates the language L iff, for some fixed, non-halting, state p of M:

L = {w : (s, ) |-M* (p, w)}.

Whenever the machine enters p, the string on the tape is enumerated.

If L is finite, then M eventually halts.

A language is Turing-enumerable iff there is a Turing machine that enumerates it.
Enumeration

Consider a printing subroutine: P be a Turing machine that enters state p and then halts:
Example of Enumeration
Let L = a*. M1 and M2 both enumerate L:

Theorem: A language is in SD iff it is Turing-enumerable.

Proof that Turing-enumerable implies SD: Let M be the Turing machine that enumerates L. We convert M to a machine M’ that semidecides L:

1. Save input w.
2. Begin enumerating L. Each time an element of L is
enumerated, compare it to w. If they match, accept.
SD and Turing Enumerable

Proof that SD implies Turing-enumerable:

If L  * is in SD, then there is a Turing machine M that semidecides L.

A procedure E to enumerate all elements of L:

1. Enumerate all w  * lexicographically.
e.g., , a, b, aa, ab, ba, bb, …

2. As each is enumerated, use M to check it.
The Other Way
Does this work?

Dovetailing

Proof that SD implies Turing-enumerable:

If L  * is in SD, then there is a Turing machine M that semidecides L.

A procedure to enumerate all elements of L:

1. Enumerate all w  * lexicographically.
2. As each string wi is enumerated:
1. Start up a copy of M with wi as its input.
2. Execute one step of each Mi initiated so far, excluding only those that have previously halted.
3. Whenever an Mi accepts, output wi.
The Other Way

M lexicographically enumerates L iff M enumerates the elements of L in lexicographic order.

A language L is lexicographically Turing-enumerable iff there is a Turing machine that lexicographically enumerates it.

Example: AnBnCn = {anbncn : n  0}

Lexicographic enumeration:
Lexicographic Enumeration

Theorem: A language is in D iff it is lexicographically Turing-enumerable.

Proof that D implies lexicographically TE: Let M be a Turing machine that decides L. Then M’ lexicographically generates the strings in * and tests each using M. It outputs those that are accepted by M. Thus M’ lexicographically enumerates L.
Lexicographically Enumerable = D

Proof that lexicographically TE implies D: Let M be a Turing machine that lexicographically enumerates L. Then, on input w, M’ starts up M and waits until:
M generates w (so M’ accepts),
M generates a string that comes after w (so M’ rejects), or
M halts (so M’ rejects).

Thus M’ decides L.
Proof, Continued

IN SD OUT
Semideciding TM H Reduction
Enumerable

D
Deciding TM AnBnCn Diagonalize
Lexic. enum Reduction
L and L in SD

Context-Free
CF grammar AnBn Pumping
PDA Closure
Closure

Regular
Regular Expression a*b* Pumping
FSM Closure
Language Summary

…, w3, w2, w1

M

M’

=w? accept

w

(enumerate L)

…, w
3
, w
2
, w
1
M
M’
=w? accept
w
(enumerateL)

…, w3, w2, w1

M

M’

∈L? accept
(enumerate
Σ* lexic.)

w

…, w3, w2, w1

M

M’

accept wi
reject

∈L?(enumerate Σ* lexic.)

…, w3, w2, w1

M

M’

=w? accept
>w? reject

M halts

w

(enumerate L
lexic.)

…, w
3
, w
2
, w
1
M
M’
=w?
accept
>w?
reject
Mhalts
w
(enumerate L
lexic.)