CSCI 4602
Fall 2001
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?

2. What is the definition of a regular language?

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

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