Topics

• The Java Computability Toolkit.
• More on Regular Expressions.
• GNFAs and converting an NFA to a regular expression.
• Converting a Regular Expression to an NFA.
• Diagonalization.
• The Pumping Lemma.

Problems to work on

1. (Warm up) Give one string that is in the language and one that is not:
   1. a*b*
   2. a(ba)*b
   3. a* + b*
   4. (b + aaa)*
   5. aba+bab
2. Write a regular expression
   1. That accepts the set of all strings.
   2. That accepts the set of all strings not containing 00 as a substring.
3. Convert to regular expressions:

   a)	b)
   c)	d)
   e)	f)
   g)

4. Convert to an NFA:
   1. (001)*(1+e)
   2. (01*0 + e + 00)
   3. (001)*(1+e)(01*0 + e + 00)
5. How long does a string in the following language have to be before we are guaranteed to have a loop?
6. Is the set of all strings that are palindromes regular? Why or why not?
7. Show that the set of all strings of zeros that have length that is a perfect cube can not be described by a regular expression.