Assignment I

Due date Sep. 24, 2003

1. Consider the following DFA over the binary alphabet:
Q = {p, q, r, s}, start state p, accepting state p.
With the following transition table:
d (p,0) = s, d (p,1) = p
d (q,0) = p, d (q,1) = s
d (r,0) = r, d (r,1) = q
d (s,0) = q, d (s,1) = r

Write the regular expression recognized by this DFA.

2. Let A be an NFA with epsilon transitions such that there are no transitions into q0 (the start state) and no transitions out of qf (the accepting state). Let L be the language recognized by A. In terms of L, describe the language accepted by the following modifications to A:
a) The automaton constructed from A by adding an epsilon-transition from qf to q0.
b) The automaton constructed from A by adding an epsilon-transition to q0 to every state reachable from q0 along any path.

3. Show that the regular expressions (L | M)* and (L*M*)* describe the same language. (some authors use "+" instead of | to denote alternation).

4. Show that the language of 0's and 1's whose strings are of the form ww, that is to say some string repeated, is not regular.

5. If L is a language and a is a symbol, then L/a, the quotient of L and a is the set of strings w such that wa is in L. Prove that if L is regular, so it L/a.

6. The complement of a language L over an alphabet S is the set of strings ver S that are not in L : S* - L. Prove that if L is regular, then its complement is regular (explain how to build the automaton for the complement).