AUCSC 315 / AUMAT 355 - Assignment 4

FINISH BY: Wednesday, 6 March 2013

  1. Proving a language is non-regular:

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

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

  2. Problem 4, chapter 10. In part (i), use the Strong Pumping Lemma (Theorem 14).

  3. 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.]

  4. Problem 6, chapter 11.

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

    1. 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.

    2. 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.)


Copyright © 2013 William W. Hackborn
Document last modified on