Ars Digita University
Theory of Computation
Recitation 3, 05/06/01

Topics

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.

Dimitri Kountourogiannis, dimitrik@alum.mit.edu