CS154 Assignment #2

Due Monday, January 24, 2000, 3:15PM

1. (10 pts.) Use the construction outlined in class and the course reader to convert the regular expression (01*0)* to an epsilon-NFA.

2. (15 pts.) Remove epsilon-transitions from your answer to (1).

3. (15 pts.) Here is a DFA:

   	0	1
   ->A	B	A
   B	C	D
   *C	F	E
   D	E	A
   E	F	D
   *F	F	B

   Find a minimal equivalent DFA. Show your work, i.e., the results of the rounds in which you discover new, distinguishable pairs of states.

4. (15 pts.) A palindrome is a string that equals its own reverse, such as 0110 or 1011101. Use the pumping lemma to show that the set of palindromes is not a regular language. Be sure to indicate clearly the steps of the ``adversarial'' argument, following the models of proofs in the reader.

5. (15 pts.) The symmetric difference of two languages L and M is the set of strings that are in exactly one of L and M. Prove that if L and M are regular, so is the symmetric difference of L and M.

   Requirements: You should read the construction for intersection in the course reader. The construction for symmetric difference is similar. You should modify this construction, rather than, say, expressing symmetric difference in terms of other operations that we know preserve regularity. Also, remember that you need not only to give a construction, but to prove that your construction is correct. Your proof should begin with the omitted induction on the length of w that is mentioned at the bottom of p. 117 of the course reader, showing that the product automaton really does simulate the automata for L and M. The ideas of the proof are not hard, but remember to state the important points, including arguments in both directions for the if-and-only-if. You also need to provide the clincher, that the accepting states of the product automaton have been correctly selected by you.

6. (15 pts.) OK; now for something a little harder. If L is a language and a a symbol, then L/a is the set of strings w such that wa is in L. For instance, if L is the language of RE (01)*, then L/1 has RE (01)*0, and L/0 is empty. Prove that if L is regular, then so is L/a. Hint: Try a construction based on a DFA for L.

7. (15 pts.) And harder still... If L is a language, define Half(L) to be the set of strings w of length n such that for some string x of length n, wx is in L. For instance, if L = {0110, 000011, 111}, then Half(L) = {01, 000}. Prove that if L is regular, so is Half(L). Hint: To start, use a DFA A for L. Design a new DFA that, after reading w, knows what A would do on any string whose length is equal to that of w. If that is not enough help, you will find another hint on the class Web page. You are free to consult it, but I would like people to think about this construction first, at least for a while.