will be based on the following problems

• from our Problems file linked above: Section 1, problems 1 through 15 and 23 through 25
• from the Sudkamp text, Chapter 2, Exercises 21, 23, 24, 26, 28, 31

will be based on the following problems

• from the Sudkamp text, Chapter 3, Exercises 1–3, 6–12.
• from our Problems file linked above: Section 3, Problems 3.1, 3.6–3.10

will be based on the following problems

• from the Sudkamp text, Chapter 4, Exercises 1–5 and 7–12

You will note that there are NO problems concerning the elimination of useless symbols. You can conclude from this that there will be no such problems on the quiz.

The supporting reading in Sudkamp for this week is Chapter 5, sections 1,2,3, and 4, and Chapter 6, section 3. The quiz will be based on the following problems.

• from the Sudkamp text, Chapter 5, Exercises 1 through 35, ommiting exercises 4 and 26. Yes, that is a lot of exercises, and you probably don't need to do all of them. Do enough so that you feel comfortable building DFAs and NFAs for relatively simple languages. Also, pay particular attention to being able to trace computations (see for instance, Example 5.2.1 on page 150)
• from the Sudkamp text, Chapter 6, Exercises 4 and 5

Here are the notes on proving languages non-regular . You can view this as a replacement for section 6.6 in Sudkamp.

The supporting reading in Sudkamp for converting NFAs to DFAs is section 5.6. But be aware that he gives an algorithm for a more complex problem, namely, that of converting NFAs with nil-moves to DFAs.

Homework problems:

• the exercises in the notes on proving languages non-regular .
• from Sudkamp, Chapter 5 Exercises, convert the following NFAs to DFAs:
  • the NFAs given on exercises 23, 24, 40. (Note that you are not asked to do those exercises as presented; just use these NFAs as practice for converting to DFAs.)

Here are the notes on constructing regular expressions from DFAs . You can view this as a replacement for section 6.2 in Sudkamp.

Homework problems:

Be able to go from a DFA to a regular expression (using Arden's Lemma) and from a regular expression to a DFA (using the route: RegExp => NFA_nil => NFA => DFA). For example, in the Sudkamp Exercises at the end of Chapter 5:

• exercises 1 (d), 2 (c, d), , 3(c), 23 (d), 24 (f).
• exercises 22, 25

Homework problems: were sent via email on Thursday 10/22

Reading: in Sudkamp, sections 8.1 and 8.2, and sections 11.1 and 11.2

Homework problems: Sudkamp exercises chapter 8, numbers 1 through 4; Sudkamp exercises chapter 11, numbers 1 and 2

Reading: in the notes on computability, sections 1 through 6 (but section 5.4 is optional).

Homework problems: from the problems in this file, do those exercises assigned by Tim after class on Wednesday 11/4. The exact set of problems will depend on how much is discussed in lecture.

Here is a version of the homework problems with solutions.

Reading: in the notes on computability, section 7. Also, in the Sudkamp text, sections 11.3 and 12.2 should be helpful.

Homework problems: the problems in this file.

Reading: in the Sudkamp text:

• sections 14.1 and 14.2.
• section 14.7 is optional, but at least have a look to see what the main result is there
• section 15.1, for the definition of time-complexity of a nondeterministic Turing Machine. You can look back at section 8.7 for the formal definition of a nondeterministic TM if you care to.
• section 15.2, for the definitions of the classes P and NP.
• Also one of the things we have to assume in the class is that you have some basic familiarity with propositional logic. (It will be crucial later.) If for some reason you do not, then you will have to play a little catch-up: read the material in Sudkamp on propositional logic, or look at the beginning of section 3 in the homework problems file:, or use some other resource, such as any discrete math text.

Homework problems: from the problems in this file:

• Problems 1.1, 1.2, 1.3, 1.4, 1.5, 1.7, 1.8, 1.10
• Problems 3.1, 3.2, 3.3, 3.4