- Proving a language is non-regular:

- Problem 1, part (ii) only, chapter 10. Use the basic
*Pumping Lemma*(Theorem 13).

- Repeat part A, but use the
*Myhill-Nerode Theorem*(Theorem 15).

- Problem 1, part (ii) only, chapter 10. Use the basic
- Problem 4, chapter 10. In part (i), use the
*Strong Pumping Lemma*(Theorem 14).

- Problem 13, chapter 10. In part (ii), explain why the
**basic***Pumping Lemma*(Theorem 13)**cannot**be used to prove that MOREA is non-regular. [The*Strong Pumping Lemma*(Theorem 14) actually**can**be used to prove that MOREA is non-regular.]

- Problem 6, chapter 11.

- Problem 15, chapter 11. Do this question in two parts, as described below:

- Cohen gives an algorithm (
*Method 2*on pages 210-211) for deciding whether the language of an FA is empty (i.e. deciding whether an FA accepts any words). Can the same algorithm be used for an NFA? If so, justify your answer. If not, state how the algorithm could be modified so that it works for an NFA.

- Cohen gives an algorithm (based on Theorem 19, which in turn is based partly on the
*Strong Pumping Lemma*, Theorem 14) for deciding whether the language of an FA with N states is infinite or finite. The algorithm basically says to try all strings with lengths greater than or equal to N and less than 2N: the language of the FA is infinite*if and only if*the FA accepts a word with a length in this range. Can the same algorithm be used for an NFA? If so, justify your answer. If not, state how the algorithm could be modified so that it works for an NFA. (To properly answer this question, you will need to read the proof of Theorem 19 on page 215.)

- Cohen gives an algorithm (

Copyright © 2013 William W. Hackborn