Ars Digita University
Theory of Computation
Recitation 2, 05/04/01

Main Topics

If we run out of things to talk about :-)

Problems to work on

  1. Write out the NFA corresponding to the language and convert to a DFA: All strings that end in 0.
  2. Same for all strings whose penultimate character is 0.
  3. If you like this sort of thing: same things for all strings that that have 0 as the third to the last character.
  4. One more if you'd like the practice: All strings ending in {0,1}
  5. Write out the NFA corresponding to this state/transition table:
                 0            1
    ->p        {p,q}         {p}
      q         {r}          {r}
      r         {s}           {}
     *s         {s}          {s}
    
    Here the star means we have an accept state
  6. Write regular expressions for all strings that end in aaba. Where Sigma is just the usual alphabet.
  7. Do the same for all strings that do not contain a.
  8. Write a regular expression for the strings that contain the substring 0101, where Sigma = {0,1}.
  9. Do the same for all strings that alternate between 0 and 1 and end in 0.
  10. Do the same for strings that alternate between 0 and 1.
  11. Hard problem: Write a regular expression for the strings over {0,1} that are divisible by 3.
  12. Hard Problem: Build an automaton that recognizes the strings that have the same number of zeros and ones.

Dimitri Kountourogiannis, dimitrik@alum.mit.edu