L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}.
Rony
Chapter20DecidableDandSemidecidableSDLanguagesFile.pptDecidable 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 = xy=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, w> : M halts on input w}
● {w: w is the email address of someone who will respond to
a message you just posted to your newsgroup}
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 .
Lemma: There is a countably infinite number of SD languages over .
Proof:
Lemma: 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
Theorem: The set D is closed 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: ML:
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 it and its complement are in SD.
Proof:
● 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.
● 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 =
{<M, w> : 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 say that Turing machine M enumerates the language L iff, for some fixed state p of M:
L = {w : (s, ) |-M* (p, w)}.
A language is Turing-enumerable iff there is a Turing machine that enumerates it.
Enumeration
Let P be a Turing machine that enters state p and then halts:
A Printing Subroutine
Let L = a*.
Example of Enumeration
Theorem: A language is 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.
w3, w2, w1 L? yes w
E
M
M'
Problem?
The Other Way
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
Unrestricted grammar
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
