| Assigned: | Wednesday, October 9 |
| Due: | Wednesday, October 16 |
We proved that the Halting Problem is not computable. What is the name of the method that we used?
Is it true that, for all languages A and B, if B is computable and A ⊆ B then A is computable? (Hint. Consider B = Σ* for some chosen alphabet Σ. What are the subsets of B?)
Prove that every finite language is computable.
Are all infinite languages uncomputable? Explain why or why not.
If A ≤m B and B is a regular language, does that imply that A is a regular language? Explain.
Show that language {p | φp(aa) = 0 and φp(bb) = 1} is not computable.
There are algorithms to convert a DFA to an equivalent regular expression and to convert a regular expression to an equivalent DFA. You can assume that.
Show that there is an algorithm that takes two regular expressions A and B and produces a regular expression C where L(C) = L(A) ∩ L(B). (Hint. Use DeMorgan's laws.)
There is an algorithm to determine whether L(M) = {} where M is a DFA. You can assume that.
Show that the set {(A, B) | A and B are regular expressions where L(A) ∩ L(B) = ∅} is computable.
What is the definition of a mapping reduction from language A to language B? Define a mapping reduction, not mapping reducibility. (Mapping reducibility is relation ≤m.)
Let H be the halting problem. If A ≤m H, can you conclude that A is not computable? Explain briefly.
Let A = {p | φp(bbb)↓} and H = {(p, x) | φp(x)↓}. Give a mapping reduction from A to H.
Is language A in the previous problem computable? Justify your answer.
Let A = {n ∈ N | n is prime}. Give a mapping reduction from A to A.
Let A = {p | φp(aa)↓} and B = {p | φp(bb)↓}. Give a mapping reduction from A to B.
Suppose that L is a language over alphabet Σ. The complement L of L is defined to be Σ* − L.
Language L is co-partially computable if L is partially computable.
Suppose that A and B are two disjoint languages over alphabet Σ. Say that language C separates A and B if A ⊆ C and B ⊆ C.
Show that, for every two disjoint co-partially computable languages A and B, there exists a computable language C that separates A and B.
Hints. Suppose that A and B are disjoint co-partially computable languages. So A and B are partially computable. That tells you that there exist programs a and b so that A = Wa and B = Wb.
Draw a Venn diagram of sets A, B and C, where C separates A and B. Remember that A and B are disjoint.
If A and B are disjoint, what can you say about set A ∪ B?
Using programs a and b, define language C by writing a program that computes it. How can your program for C be sure that it answers yes on every input that is in A and answers no on every input that is in B?