Due date Oct. 2.
1. Given a language L defined over some alphabet S, we define the Lc,
the complement of L as the language consisting of all strings in S* which
do not belong to L. Prove that if L is a regular language, then Lc is also
a regular language.
2. From text: 1.24. The reversal of a regular language is a regular language.
3. From text: 1.25. This proves that a finite automaton can verify (or perform)
addition if both operands are presented one bit at a time.
4. From text: 1.17 (applications of the pumping lemma).
5. From text: 1.36: correct arithmetic expressions do not constitute a