CS 575, Spring '16, Homework 5

Due on FRIDAY March 25th, at the beginning of class

1. Give a regular expression for the language of odd-lengthed strings over {0,1} that contain the substring 00.

2. Give a regular expression for the language of strings over {a,b} that do not contain the substring aa.

3. Draw a finite automaton for the language in (1).

4. Draw a finite automaton for the language in (2).

5. Describe the language generated by this regular expression in simple English.

(0 U 1)*0(0 U 1)*0(0 U 1)*

Here, "U" denotes the union symbol as Sipser uses it, also known as Or, or |, or +, depending on the source you use.