Computer Science 4602, Fall 2018
Assignment 3

Numbered exercises are from Sipser, third edition, beginning on page 83 for Chapter 1 and 187 for Chapter 3. Exercise 4.20 is on page 212.

1. 1.20(a-d)
2. 1.22
3. 1.41
4. 3.6
5. 3.13

6. 4.20.
   Hints. A language is co-Turing-recognizable if its complement is Turing-recognizable (partially computable). Suppose that A and B are disjoint co-Turing recognizable languages. So A and B are Turing-recognizable.

   1. Draw a Venn diagram of sets A, B and C. Remember that A and B are disjoint.

   2. If A and B are disjoint, what can you say about set A ∪ B?

   3. If a problem is Turing-recognizable, you can assume that you have a recognizer for it. Remember that a recognizer for L stops and answers yes on all inputs that belong to L (but might not stop at all on inputs that do not belong to L). Give names to recognizers that you know exist, and say which sets they recognize.

   4. Using the recognizers from step 3, produce the set C by writing a program that decides it. (The program serves as C's definition.) How can your decider for C be sure that it says yes on every input that is in A and says no on every input that is in B?

7. There are algorithms to convert a DFA to an equivalent regular expression and to convert a regular expression to an equivalent DFA. (We skipped that due to Hurricane Florence.) 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).

8. Show that the set {(A, B) | A and B are regular expressions where L(A) ∩ L(B) = ∅} is computable.