Assignment III

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 regular language.