CS 4384 — Automata Theory, Homework 3
Show that the language is not regular.
We show this by the pumping lemma.
- Let
- Let . Note that and
- Consider factorization and and
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.
- Thus the language is not regular
Let . Show that the language is not regular.
- Let
- Let . Note that and
Consider factorization and
- Note that .
- Let . Then . With ,then , which is not in the language since
- 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
- Let
- Let , where . Note that and
- Consider factorization and
- 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 .
- Thus the language is not regular.