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.
- Remember to show your work and explain your answers.
Correct answers without complete explanations won't receive full credit.
Incorrect answers with explanations may receive partial credit.
- See the course webpage for
the late homework submission policy.
- Homework Problems:
- I. For each of the following regular expressions:
- 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.
- 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
- Convert the finite automaton into an equivalent regular expression
using the process explained in Section 6.2. Show the whole process.
- 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:
- 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.
- 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.