CSCI 250 (GOLDWEBER)
Spring 08: 1/18/06 Homework 1 Due Date: Friday January 25, 2008.

The exercises are from the end of Chapter 2 on page 54 of the text.

There is a possible 45 points for this homework assignment.

Problem 1. (9 pts.) Describe the language accepted by the automatons from problems 2.1, 2.2 and 2.6. Since there are three different automatons, you should provide a description for three different languages.

Problem 2. (4 pts.) Exercise 2.3

Problem 3. (4 pts.) Exercise 2.4

Problem 4. (6 pts.) Exercise 2.7

Problem 5. (4 pts.) Exercise 2.9

Problem 6. (18 pts.) For each of the following regular expressions, draw a DFA or NFA recognizing the corresponding language.

1. Any string over {0, 1} which ends in a 0.
2. Any string over {11, 10}.
3. Any string over {0, 1} which contains either a 1 or 00.
4. Any string over {111, 100} and that has a final ending 0.
5. The strings 0, or a 1 followed by zero or more 0's, or any string over {0, 1} which begins and ends with a 0 and has zero or more 1's in between.
6. Any string over {0, 1} which ends in either 01 or 110.

Problem 7. (6 pts. Extra Credit) Exercise 2.5

Problem 8. (5 pts. Extra Credit) Exercise 2.10

---

File translated from T_EX by T_TH, version 3.74.
On 16 Jan 2008, 11:24.