READING & HOMEWORK ASSIGNMENTS


Assignments are listed here chronologically by due date. New assignments will tend to be at the bottom of the page.

Last modified:

Jump directly to Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10

The author of the textbook maintains a list of errata.


Week 2: Wednesday

  • Homework Problems for Wednesday of Second Week:
    • No new problems.

  • Reading Assignment for Wednesday of Second Week:
    • Be sure to have read Section 1.4.

  • Discussion Questions for Wednesday of Second Week:
    • Finish DQs from Monday.
    • Convert the NFAs from Figures 1.6 and 1.42 to regular expressions.

  • New material for Wednesday of Second Week:
    • No new material. Keep working on material from Monday.

Week 3: Friday

  • Homework Problems for Friday of Third Week:
    • Exercise 2.13.

  • Reading Assignment for Friday of Third Week:
    • Read Section 2.2.

  • Discussion Question for Friday of Third Week:
      No new DQs

  • New material for Friday of Third Week:
    • Finish Exercises 2.4 , 2.6, and 2.16 as listed on Wednesday of Third Week.
    • Theorem 2.9.
    • Example 2.10.
    • Problem 2.26.
    • Example 2.16.
    • Parts b, c, e of Exercises 2.5 and 2.7.
    • Lemma 2.21
    • Proof idea for Lemma 2.27.

  • Reading Assignment for Monday of Fourth Week:
      Read Section 2.3.

  • Exam 1 will be outside of class on Thursday or Friday of this week.

  • Discussion Questions for Monday of Fourth Week
  • New material for Monday of Fourth Week:
    • Lemma 2.21 (you may use Example 2.25 to help explain) and Proof idea for Lemma 2.27 as listed on Wednesday of Third Week.
    • Theorem 2.20.
    • Exercise 2.11.
  • Week 4: Wednesday

    • Exam 1 will be made available and should be completed NO LATER than Monday Week 5.

    • Reading Assignment for Wednesday of Fourth Week:
    Week 4: Thursday
      Small group meetings
    Week 4: Friday
      TBD


    Week 5: Monday

    • Homework Problems for Monday of Fifth Week:
        No problems due today.

    • Reading Assignment for Monday of Fifth Week:
      • Be sure to have read Section 2.2 and start reading Section 2.3

    • Discussion Questions and New Material for Monday of Fifth Week:
      • Finish material from 4th Week.
      • Theorem 2.34.
      • Problem 2.18.
      • Problem 2.30.
      • Problem 2.31.

  • (Ben) Exercise 3.2 (d).
  • (Alec) Exercise 3.5.
  • (Chelsea, Kevin, Evan) Exercise 3.8, giving higher-level descriptions.
  • (All) Look at examples #1-6 of Turing Machines. Describe the languages recognized by these machines.--> Week 5: Wednesday

    • Homework problems for Wednesday of Fifth Week:
      • Exercise 2.2 (Due date extended to M6).
      • Exercise 2.12 (Due date extended to F5).

    • Reading Assignment for Wednesday of Fifth Week:
      • Be sure to have read Section 2.3.

    • Discussion questions & new material for Wednesday of Fifth Week:
        TBD
    Week 5: Thursday
      Small group meetings to go over pumping lemma examples. NOTE: I cannot meet with the in-person group at 11AM. If you are in that group, please attend another of the groups if you are available.
    Week 5: Friday

    • Homework Problem for Friday of Fifth Week:
      • Exercise 2.12 (from Wednesday Week 5)
      • (Optional challenge) Convert the PDA for the language of palindromes over {0, 1} into an equivalent CFG.

    • Reading Assignment for Friday of Fifth Week:
      • No new reading.

    • Discussion Questions for Friday of Fifth Week:
      • NO CLASS MEETING

  • Week 6: Wednesday
    • Homework Assignment for Wednesday of Sixth Week:
        Turn in HW from M6 if you haven't already

    • Reading Assignment for Wednesday of Sixth Week:
        No new reading.

    • Discussion Questions for Wednesday of Sixth Week:
      • Finish DQs from Wednesday W5.
    Week 6: Thursday
      Small group meetings to go over Turing machine examples.

  • Discussion Questions for Friday of Sixth Week:
    • NO CLASS MEETING


    Week 7: Monday

  • Reading Assignment for Monday of Seventh Week:
    • Finish reading Sections 3.2 and 3.3.

  • Discussion Questions and New Material for Monday of Seventh Week:
      -->
    • Problem 3.22.
    • Theorem 3.13.
    • Theorem 3.16.
    • Corollaries 3.15, 3.18, 3.19.
    • Theorem 3.21.
    • Church-Turing Thesis.
  • Week 7: Wednesday

    • Homework problem for Wednesday of Seventh Week:
      • Problem 3.11.

    • Reading Assignment for Wednesday of Seventh Week:
    DAY BEFORE CLASS IN-CLASS TOPIC/ACTIVITY
    Mon 1
    Introductions
    Course, People
    Syllabus Highlights

    Work on Reflection A for Wednesday
    Wed 1
    To Be Submitted on Kit
    Reflection A

    Readings
    Chapter 0 (Everything after Section 0.1 should be review)
    Section 1.1

    An Example-Based Introduction to Finite-State Machines
    Discussion Questions
    Give state diagrams of deterministic finite automata recognizing the following languages. In all cases the alphabet is {0,1}.
    • {w | w begins with a 1 and ends with a 0}.
    • {w | w has length at least 3 and its third symbol is a 0}.
    • {w | w doesn't contain the substring 110}.
    • {w | w contains at least two 0s and at most one 1}.
    • {w | w contains an even number of 0s or exactly two 1s}.
      (These are parts a, d, f, j, and l of 1.6.)

    New material for small groups
    • Explain the differences between an NFA and a DFA.
    • Give an example of an NFA and show how it computes, by tracing through several accepting and non-accepting inputs.
    • Discuss the formal definition of an NFA.
    • Work through Example 1.41.
    • Work through Theorem 1.39 on the equivalence of NFAs and DFAs.

    Start working on
    Problems 1.14 and 1.48 from Sipser
    Fri 1
    To Be Submitted on Kit
    Problem 1.48 from Sipser

    Readings
    Read Section 1.2
    Read Section 1.3

    Discussion Questions
    Give NFAs with the specified number of states recognizing each of the following languages. In all cases the alphabet is {0,1}.
    1. Exercise 1.7 b.
    2. Exercise 1.7 e.
    3. Exercise 1.10 b.
    4. Exercise 1.10 c.
    5. The language containing only the empty string with one state.
    Exercise 1.16 a.
    Exercise 1.16 b.
    The class of regular languages is closed under union.
    The class of regular languages is closed under concatenation.
    The class of regular languages is closed under intersection.
    The class of regular languages is closed under the star operation.
    Exercise 1.15.

    New material for small groups
    Give regular expressions generating the following languages. In all cases the alphabet is {0,1}.
    (The following are parts b, d, f, j, a nd l of Exercise 1.18.)
    1. {w | w contains at least three 1s}.
    2. {w | w has length at least 3 and its third symbol is a 0}.
    3. {w | w doesn't contain the substring 110}.
    4. {w | w contains at least two 0s and at most one 1}.
    5. {w | w contains an even number of 0s or exactly two 1s}.
    Lemma 1.55.
    Example 1.58.
    Describe the idea behind the proof of Lemma 1.60, define GNFAs.
    Example 1.66.
    Example 1.68.
    Exercise 1.21 b.

    Work on
    Problems 1.31 and 1.32 from Sipser
    Mon 2
    To Be Submitted on Kit
    Problems 1.14, 1.31 and 1.32

    Readings
    Read Section 1.4.
    Discussion Questions
    Are the regular expressions 0*(10+)*1* and (0 U 10)*1* equivalent? Are any of these equivalent to your answer in the previous problem?
    Exercise 1.19, parts a and b.
    Part c of Exercise 1.28.
    (The following is Problem 1.36.) Let Bn = { ak | where k is a multiple of n}. Show that for each n >= 1, the language Bn is regular.

    New material for small groups
    Theorem 1.70.
    Example 1.73.
    Exercise 1.29.
    Wed 2
    Readings
    No new readings. Be sure to have read Sections 1.1 - 1.3.
    Discussion Questions and New Material
    Finish discussion questions and new material from Friday 1 and Monday 2.

    Convert the NFAs from Figures 1.6 and 1.42 to regular expressions.
    Thurs 2
    Help session with Mallory
    8 - 10 PM OU 207
    Fri 2
    Readings
    Make sure you've read Section 1.3.
    Start reading Section 1.4
    Discussion Questions
    Discuss Lemma 1.55, Example 1.58, GNFAs, Lemma 1.60, Example 1.66, Example 1.68.
    Work through Exercise 1.21
    Find a RE for the language of strings over the alphabet {a, b} that do not contain the substring aba.

    Homework
    Convert the NFA in the diagram below to a regular expresssion. Follow the process outlined in Theorem 1.60 and show your work.
    Mon 3
    Readings
    Be sure you've read Section 1.4.
    Watch the video What is the Pumping Lemma
    Watch the video Nonregular languages: How to use the Pumping Lemma
    Discussion Questions
    Finish converting the NFA in 1.21(b) to a regular expression.
    Convert the NFAs from Figures 1.6 and 1.42 to regular expressions.

    New material
    Theorem 1.70
    Example 1.73
    Exercise 1.29
    (The following is Exercise 1.30.) Describe the error in the following "proof" that 0*1* is not a regular language. (An error must exist because 0*1* is regular.) The proof is by contradiction. Assume that 0*1* is regular. Let p be the pumping length for 0*1* given by the pumping lemma. Choose s to be the string 0p1p. You know that s is a member of 0*1*, but Example 1.73 shows that s cannot be pumped. Thus you have a contradiction. So 0*1* is not regular.

    Exercise 1.55

    Homework problems
    Prove that the language {w | w is a palindrome} over the alphabet {0, 1} is not regular. (A palindrome is a string that reads the same forward and backward.)

    Problem 1.35 (Come see me if you need a hint for what string to choose).
    Wed 3
    Fri 3
    To Be Submitted on Kit
    NFA to RE conversion from Friday Week 2

    Readings
    Read Section 2.1
    Discussion Questions
    Examples 1.74, 1.75, 1.76, 1.77
    Exercises 1.29, 1.46, 1.55

    New material
    Define context-free grammars (CFGs) and give an example.

    Discuss process of designing CFGs.

    Exercise 2.3.

    Exercise 2.4

    Exercise 2.6

    Discuss ambiguity and do exercise 2.8

    Consider the grammar with rules
    • S -> aaB
    • A -> bBb|epsilon
    • B -> Aa.
    Show that the string aabbabba is not in the language generated by this grammar.

    Exercise 2.16

    Thurs 3
    Study session with Mallory
    8 - 10 PM OU 207
    Mon 4
    Readings
    Be sure you've read Section 2.1
    DQ and New Material
    Continue with material from Week 3
    Wed 4
    Fri 4
    To be Submitted on Kit
    The two pumping lemma problems assigned on Friday Week 2

    Readings
    Read Section 2.2
    Discussion Questions
    Exercises 2.6, 2.16 (from M4)

    New Material
    Theorem 2.9
    Example 2.10
    Problem 2.26
    Definition 2.13
    Examples 2.14, 2.16, 2.18
    Exercises 2.5 b, c, e
    Exercise 2.7
    Theorem 2.20
    Exercise 2.11
    Problem 2.18

    Homework Problems
    Exercises 2.13. 2.14, 2.17
    Mon 5
    To be Submitted on Kit:
    Exercises 2.13, 2.14, 2.17

    Reading
    Finish reading Section 2.2 and start reading Section 2.3
    Discussion Questions and New Material:
    Convert the following grammar into Chomsky Normal Form:
    S -> ( S ) S
    S -> epsilon
    Describe the language generated by this grammar.

  • Exercise 2.5(e) and 2.7 as previously listed.
  • Give an informal description and a state diagram of a PDA for the language {w | w contains more 1s than 0s}, over the alphabet {0, 1}.
    Continue with new material from F4

    Homework Problem
    Exercise 2.12
    Wed 5
    Readings
    Finish reading Section 2.3
    Discussion Questions and New Material:
    Theorem 2.34
    Examples 2.36, 2.37, 2.38
    Work on Problem 2.30
    Fri 5
    Readings
    Read Section 3.1
    Discussion Questions and New Material:
    Discuss Problem 2.30 b, c
    Discuss Problem 2.18
    Introduce definitions (Turing machine, various types of configurations, Turing-recognizable, Turing-decidable)
    Example 3.7
    Example 3.9
    Example 3.11
    Example 3.12

    Homework Problem
    Exercise 2.2
    Mon 6
    To be Submitted on Kit:
    Exercises 2.12, 2.2

    Readings
    Read Sections 3.1 and 3.2.
    Discussion Questions and New Material
    Definitions (Turing machine, various types of configurations, Turing-recognizable, Turing-decidable)
    Example 3.7.
    Example 3.9.
    Example 3.11.
    Example 3.12
    Exercise 3.2 (d).
    Exercise 3.5.
    Exercise 3.7.
    Exercise 3.8, giving higher-level descriptions.
    Look at examples #1-6 of Turing Machines. Describe the languages recognized by these machines. (Some of you explored these a little in COMP105, but some of you never took COMP105. In either case, it's good to take a look at them now with more experienced eyes!)
    Problem 3.15.
    Problem 3.16

    Homework
    Regular language reflection (due Wed 6)
    Wed 6
    Readings
    Be sure you have read Sections 3.1 and 3.2
    NO CLASS MEETING.
    Work on reflection and DQs from Mon 6.
    Fri 6
    To be Submitted on Kit:
    Regular language reflection

    Readings
    Read Sections 3.2 and 3.3.
    Read the Chapter on Turing "Turing Conceives of the All-Purpose Computer" that is posted on Kit.
    Check out these videos to see physical Turing machines that people have actually built:
    A Turing machine - Overview

    The only working Turing machine there ever was probably
    Discussion Questions and New Material
    Finish DQ and new material from Mon 6
    Theorem 3.13
    Theorem 3.16
    Corollaries 3.15, 3.18, 3.19
    Explain the difference between a decider and a recognizer.

    Homework Problem
    Problem 3.11
    Mon 7
    Readings
    Be sure to have read Sections 3.2 and 3.3
    Discussion Questions and New Material
    Finish DQ and new material from F6
    Church-Turing Thesis
    Algorithms and Turing machines

    Homework Problem
    Research real-world applications of DFAs, NFAs, PDAs, CFGs. Find two that are interesting to you and submit a short summary of each. At the end of your summaries, you should include any links or references to the applications you found.
    Wed 7
    To be Submitted on Kit
    Problem 3.11

    Reading
    Read Section 4.1.
    Discussion Questions and New Material
    Theorem 4.1.
    Theorem 4.2.
    Theorem 4.3.
    Theorem 4.4.
    Theorem 4.5.
    Theorems 4.7 - 4.9.
    Exercise 4.2.
    Exercise 4.3.
    Exercise 4.5.
    Exercise 4.6.
    Problem 4.10.
    Problem 4.16.
    Problem 4.25.
    Fri 7
    DOGL
    Mon 8
    Readings
    Finish Section 4.1
    Start Section 4.2
    Discussion Questions and New Material
    Theorems 4.7 - 4.9 (from Week 7)
    Problems 4.11, 4.12

    Work on getting previous homework finished

    Homework Problems
    Problems 4.13, 4.21, 4.26, 4.28
    Wed 8
    Readings
    Keep reading Section 4.2
    Work on homework problems
    Fri 8
    Readings
    Finish reading Section 4.2
    Discussion Questions and New Material
    Theorem 4.11
    Corollary 4.18
    Theorem 4.22
    Corollary 4.23
    Mon, Wed 9
    Readings
    Read Sections 5.1 and 5.3
    Discussion Questions and New Material
    Theorem 5.1 - 5.4
    Theorem 5.13
    Exercises 5.1, 5.2
    Problem 5.13
    Theorem 5.22, Corollary 5.23
    Examples 5.24, 5.26
    Theorem 5.28, Corollary 5.29
    Theorem 5.30
    Exercise 5.5
    Problem 5.28 (Rice's Theorem)

    Homework Problems
    Problems 5.9, 5.22 (You may submit these in groups, one person submits and invites the others on Kit)
    Fri 9
    Readings
    Read Sections 7.1, 7.2
    Discussion Questions and New Material
    Definitions 7.2, 7.5 and their examples
    Definition 7.7 and the example involving the language A = {0k1k | k >= 0}.
    Theorem 7.8
    Definition 7.9
    Theorem 7.11
    Definition 7.12
    Theorems 7.14, 7.15, 7.16
    Exercises 7.1, 7.2, 7.8, 7.9

    Reflection
    Work on the Relfection on Context Free, Turing-Decidable, and Turing-Recognizable Languages before Friday of Week 10
    Week 10
    Reading
    Read some more in Chapter 7
    Discussion Questions and New Material
    Group discussion of P, NP, NP-Complete. Submit summary on Kit

    Complete your Final Reflection by NOON on Tuesday, June 6.

    Week 7: Thursday

      Small group meetings to go over decidable problems from DQs

    Week 7: Friday

    • Homework problem for Friday of Seventh Week:
      • Problem 3.11. (If you haven't already submitted it on W7.)

    • Reading Assignment for Friday of Seventh Week:
      • Section 4.2.

    • Discussion Questions and New Material for Friday of Seventh Week:
      • No class meeting


    Week 8: Monday

    • Reading Assignment for Monday of Eighth Week:
      • Finish reading Chapter 4.

    • Discussion Questions and New Material for Monday of Eighth Week:
      • Exercise 4.5 (not in 2nd edition).
      • Problem 4.10 (4.9 in 2nd edition).
      • Problem 4.16 (4.15 in 2nd edition.
      • Problem 4.25 (4.23 in 2nd edition).
      • Theorem 4.11.
      • Corollary 4.18.
      • Theorem 4.22.
      • Corollary 4.23.
    Week 8: Wednesday and Friday

    • Homework problems for Friday of Eighth Week:
      • Problems 4.13 (4.12 in 2nd edition), 4.21 (4.19 in 2nd edition), 4.26 (4.24 in 2nd edition), 4.28 (4.26 in 2nd edition).

    • Reading Assignment for Wednesday of Eighth Week:
      • Read Sections 5.1, 5.3.

    • Discussion Questions and New Material for Wednesday and Friday of Eighth Week:
      • Theorem 4.11.
      • Corollary 4.18.
      • Theorem 4.22.
      • Corollary 4.23.
      • Theorem 5.1.
      • heorem 5.2.
      • Theorem 5.3.
      • Theorem 5.4.
      • Exercise 5.1.
      • Exercise 5.2.
      • Problem 5.13.
      • Theorem 5.22 & Corollary 5.23.
      • Example 5.24.
      • Example 5.26.
      • Exercise 5.5.
      • Problem 5.28.

    • Exam 2 will be available by the end of Eighth Week, and will be due by the end of Ninth Week.
    Week 8: Thursday
      Small groups to go over decidabilty Thms and DQs

    Week 9

    • Reading Assignment for Ninth Week:
      • Read Sections 5.1, 5.3.

    • Discussion Questions and New Material for Ninth Week:
        Start/Continue with Reducibilty Thms and Exercises
      • Theorem 5.1.
      • Theorem 5.2.
      • Theorem 5.3.
      • Theorem 5.4.
      • Exercise 5.1.
      • Exercise 5.2.
      • Problem 5.13.
      • Theorem 5.22 & Corollary 5.23.
      • Example 5.24.
      • Example 5.26.
      • Theorem 5.28, Corollary 5.29.
      • Theorem 5.30.
      • Exercise 5.5.
      • Problem 5.28.


    Week 10

    • Homework Questions for Tenth Week:
      • Problems 5.9 and 5.22. These may be done in groups, where each group submits one set of solutions with all group member names.

    • Reading Assignment for Tenth Week:
      • Read Chapter 7.

    • Discussion Questions and New Material for Tenth Week:
      • Definitions 7.2, 7.5 and examples.
      • Definition 7.7 and example involving language A = {0k1k| k >= 0}.
      • Theorem 7.8.
      • Definition 7.9 & Theorem 7.11.
      • Exercise 7.5.
      • Exercise 7.6.
      • Exercise 7.7.
      • Exercise 7.12.
      • Definition 7.12.
      • Theorem 7.14.
      • Theorem 7.15.
      • Theorem 7.16.
      • Problem 7.15.
      • Exercise 7.8.
      • Exercise 7.10.

    • The final reflection will be distributed on or before Wednesday, and will be due on Kit by Monday, June 7.