### CS3133 Foundations of Comptuter Science Homework 3 - A Term 2009

#### PROF. CAROLINA RUIZ

Due Date: Friday Oct. 2, 2009 at 10:00 am
See course policy regarding late homework submissions

• Homework Instructions:
• Read Sections 6.1-6.6) of the textbook in detail.
• This is an individual homework. No collaboration is allowed.
• Submit a hardcopy of your written homework solutions by the beginning of class (i.e., 10:00 pm) the day the homework is due.
• See the course webpage for the late homework submission policy.

• Homework Problems:

• I. For each of the following regular expressions:
1. Construct a finite automaton (either DFA or NFA) that accepts the same language described by the regular expression using the process explained in Section 6.1. Show the whole process.
2. Convert your finite automaton into an equivalent regular grammar using the process explained in Section 6.3. Show the whole process.

• II. For each of the following finite automata:
• The NFA from Chapter 5 Problem 23
• The NFA from Chapter 5 Problem 36
1. Convert the finite automaton into an equivalent regular expression using the process explained in Section 6.2. Show the whole process.
2. Convert the finite automaton into an equivalent regular grammar using the process explained in Section 6.3. Show the whole process.

• III. For each of the following regular grammars:
1. Construct a finite automaton (either DFA or NFA) that accepts the same language generated by the regular grammar using the process explained in Section 6.3. Show the whole process.
2. Convert your finite automaton into an equivalent regular expression using the process explained in Section 6.2. Show the whole process.

• IV. Solve the following problems from your textbook: Chapter 6: Problems: 7, 14 a-d and f (that is, all but e) , 15, 16.