CSCI 4602
Fall 2001
Answers to practice questions for quiz 2

1. Does there exist a language that can be described by a regular expression but that is not the language of any deterministic finite state machine?

   No. Regular expressions and deterministic finite state machines have exactly the same power for describing or recognizing languages.

2. What is the definition of a regular language?

   There are many equivalent definitions. A language X is regular if there is a DFA M such that L(M) = X. An alternative definition is that X is regular if there exists a regular expression E such that L(E) = X.

3. Show that the language {aⁿba²ⁿ | n > 0} is not regular. This language contains strings {abaa, aabaaaa, aaabaaaaaa, ...}.

   The proof is by contradiction. Let Z = {aⁿba²ⁿ | n > 0}. Suppose that Z is a regular language. Then there must be a DFA M such that L(M) = Z.

   Try running M on each of the strings a, aa, aaa, aaaa, ... (arbitrarily many a's). Since M has finitely many states, there must be two different ones of those strings, say aⁱ and a^j, on which M ends at the same state. Since M reaches the same state on aⁱ and a^j, it must also reach the same state on aⁱx as on a^jx, for every string x. Since M ends on the same state for both, it must give the same answer for aⁱx as for a^jx.

   Consider x = ba²ⁱ. The correct answer on input aⁱba²ⁱ is "yes". The correct answer on input a^jba²ⁱ is "no". But M has to give the same answer on both. Clearly, M gives the wrong answer on one of those inputs, so L(M) is not Z. That contradicts the presumption that L(M) is Z.

4. If L is a language then L² is the language {xy | x in L and y in L}. Show that the regular languages are closed under squaring. That is, if L is regular then so is L².

   The regular languages are closed under concatentation (proved in class). Since A is regular, so is AA. But AA = A². So A² is regular.