## Ars Digita University

Theory of Computation

Recitation 3, 05/06/01

## 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

- (Warm up) Give one string that is in the language and one that is not:
- a*b*
- a(ba)*b
- a* + b*
- (b + aaa)*
- aba+bab

- Write a regular expression
- That accepts the set of all strings.
- That accepts the set of all strings not containing 00 as
a substring.

- Convert to regular expressions:
- Convert to an NFA:
- (001)*(1+e)
- (01*0 + e + 00)
- (001)*(1+e)(01*0 + e + 00)

- How long does a string in the following language have to be before
we are guaranteed to have a loop?
- Is the set of all strings that are palindromes regular? Why or why not?
- 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.

Dimitri Kountourogiannis, dimitrik@alum.mit.edu