Due Dates:  Oral presentations of material begin on 15 September.
Written descriptions of material presented due one week after presentation.
Topics: Regular Expressions (Chapter 1).

An integral part of this class is understanding and presenting the problems assigned as homework. Everyone is expected to do all the problems, but we will take turns on who presents the problem solutions to the class (every 2-3 weeks, depending on the number of students in the class). Within a week of presenting a problem solution to the class, you must submit a written description of it, via the Blackboard system. The written solutions will be posted on the Blackboard website for the class, so, they can used by everyone to study for the exams. Since it's hard to write down answers that are concise and are easily readable by all, if you wish to improve a grade on any problem, you may resubmit it for grading.

Undergraduate Problems

All students enrolled should complete the following:

  1. For the language, (aaa)*, give two strings that are members of the language and two strings that are not members-- a total of four strings.
    (assume that the alphabet is {a,b}.)
  2. For the language, aΣ*b, give two strings that are members of the language and two strings that are not members-- a total of four strings.
    (assume that the alphabet is {a,b}.)
  3. Are these languages the same: a*b* = a* ∪ b*? Explain why or give a string that is a member of one language and not the other.
    (assume that the alphabet is Σ = {a,b}.)
  4. Give a state diagram of an NFA that recognizes the following language:
    0*1*0*0 with three states.
    (assume that the alphabet is {0,1}.)
  5. Give a state diagram for an NFA that recognizes the star of the language described in Problem Set 1, UG#2:
    {w | w contains at least 3 1s}

Graduate Problems

Students enrolled for graduate credit, should complete all the undergraduate problems, as well as:

  1. For the language, (ε ∪ a)b, give two strings that are members of the language and two strings that are not members-- a total of four strings.
    (assume that the alphabet is {a,b}.)
  2. Use the procedure described in Lemma 1.29 (and in lecture in class) to convert the following regular expressions to nondeterministic finite automata:
    (0 ∪ 1)*000(0 ∪ 1)*
    (assume that the alphabet is {0,1}.)
  3. Show that if M is a DFA that recognizes language B, swapping the accept and non-accept states in M yields a new DFA that recognizes the complement of B. Conclude that the classs of regular languages is closed under complement.