Ars Digita University
Theory of Computation
Recitation 3, 05/06/01
- The Java Computability Toolkit.
- More on Regular Expressions.
- GNFAs and converting an NFA to a regular expression.
- Converting a Regular Expression to an NFA.
- The Pumping Lemma.
Problems to work on
- (Warm up) Give one string that is in the language and one that is not:
- a* + b*
- (b + aaa)*
- Write a regular expression
- That accepts the set of all strings.
- That accepts the set of all strings not containing 00 as
- Convert to regular expressions:
- Convert to an NFA:
- (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, email@example.com