CS 4384 — Automata Theory, Homework 3

Download PDF

Show that the language is not regular.

We show this by the pumping lemma.

  1. Let
  2. Let . Note that and
  3. Consider factorization and and
  4. Let

    • Observe that , by the definition of the power of a string. Further observe that will always remove the prefix “b”, since . For , with , which is not in the language.
  5. Thus the language is not regular

Let . Show that the language is not regular.

  1. Let
  2. Let . Note that and
  3. Consider factorization and

    1. Note that .
  4. Let . Then . With ,then , which is not in the language since
  5. Therefore, the language is not regular, since regular languages are closed under complement, which implies that nonregular languages are also closed under complement.

Construct a CFG for using the recursion method. (That is, you should first define L recursively and extract the CFG rules from it.)

The smallest string in the language is clearly , then . Continuing, we see that the number of s increases 3 at a time, and the number of s two at a time.

Let

Show that Y is not regular: Hint(You can use the pumping lemma)

  1. Let
  2. Let , where . Note that and
  3. Consider factorization and
  4. Let . is contained within the term. + Thus, the removal of some nonzero amount of characters characters from is no longer unique, which violates that , since is an within the string for some .
  5. Thus the language is not regular.