1. Construct state diagrams of NFA's accepting languages specified by the following regular expressions:
2. Problem 1.16(a), page 86 of the text.
3.
Prove that the following languages over 
are not regular:
4.
Prove that the language 
is not
regular.
5.
Problem 1.36, page 89 of the text.
Note: The problem asks you to show that no DFA will
accept all strings representing valid binary additions, and only those
strings. On the other hand, there is a simple 2 state DFA with
output that computes the sum of two numbers written in binary; we did
this example in class. This shows that sometimes the way we formalize the
problem (as a yes/no problem, or as an input-output problem) leads to
different conclusions as far as the ``difficulty'' of the problem is
concerned.
Extra credit.
Let L be an arbitrary subset of 
. Prove that 
is regular.
Does the claim remain true when L is an arbitrary subset of 
?