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 1: Wednesday

  • Reading Assignment for Wednesday of First Week:

  • Discussion Questions to try for class Wednesday of First Week:
    • Give state diagrams of deterministic finite automata recognizing the following languages. In all cases the alphabet is {0,1}.
      1. {w | w begins with a 1 and ends with a 0}.
      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}.
        (These are parts a, d, f, j, and l of 1.6.)

  • New material for small groups on Wednesday of First Week:
    • 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.

Week 1: Friday

  • Homework Problems for Friday of First Week:
    • Exercise 1.14:
      1. Show that, if M is a DFA that recognizes language B, swapping the accept and nonaccept states in M yields a new DFA that recognizes the complement of B. Conclude that the class of regular languages is closed under complement.
      2. Show by giving an example that, if M is an NFA that recognizes language C, swapping the accept and nonaccept states in M doesn't necessarily yield a new NFA that recognizes the complement of C. Is the class of languages recognized by NFAs closed under complement? Explain your answer.
    • Problem 1.48:

      Let

      D={w | w contains an equal number of occurrences of the substrings 01 and 10}.
      Thus 101 is in D because 101 contains a single 01 and a single 10, but 1010 is not in D because 1010 contains two 10s and one 01. Show that D is a regular language by constructing a finite automaton that recognizes D.

  • Reading Assignment for Friday of First Week:
    • Read Section 1.2.
    • Read Section 1.3.

  • Discussion Questions to try for Friday of First Week:
    • 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 on Friday of First Week:
    • 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.

Week 2: Monday

  • Homework Problems for Monday of Second Week:
    • Problems 1.31 and 1.32.

  • Reading Assignment for Monday of Second Week:
    • Read Section 1.4.

  • Discussion Questions for Monday of Second Week:
    • Start with regular expression #4 from Friday Week 1 and finish new material from Friday.
    • Find a regular expression for {w | w doesn't contain the substring 110}. (This was from Friday.)
    • 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 Monday of Second Week:
    • Theorem 1.70.
    • Example 1.73.
    • Exercise 1.29.

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 2: Friday

  • Reading/Watching for Friday of Second Week:
  • Discussion Questions for Friday of Second Week:
    • Convert the NFAs from Figures 1.6 and 1.42 to regular expressions. (From Wednesday)
    • Exercise 1.46.
  • New material for Friday of Second Week:
    • Finish new material from Monday and Wednesday.
    • (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
  • Reflection due before class on Monday Week 3:

      Discuss each of the following:

    • What does it mean for a language to be regular? What does it mean for a language to not be regular?
    • How do you prove a language is regular? How do you prove a language is not regular?
    • Which discussion question(s) have contributed the most to your understanding of regular languages so far? Discuss why/how they have contributed to your understanding.

Week 3: Monday

    All things Pumping Lemma!

Week 3: Wednesday

  • Homework Problems for Wednesday of Third Week :
    • 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).

  • Reading Assignment for Wednesday of Third Week:
    • Read Section 2.1

  • Discussion Questions for Wednesday of Third Week:
    • Exercise 1.46 (From F2)

  • New material for Wednesday of Third Week:
    • Define context-free grammars (CFGs) and give an example.
    • Discuss process of designing CFGs.
    • Exercise 2.3 part o.
    • 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

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.

Week 4: Monday

  • Homework Problems for Monday of Fourth Week:
    Due Date extended until Wednesday.
    • Exercise 2.14.
    • Exercise 2.17.

  • 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
    • 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}.

  • 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:
    • Be sure to have read Section 2.3.

  • New Material for Wednesday of Fourth Week:
    • Finish any material left from Monday of Fourth Week.
    • Theorem 2.34.
    • Problem 2.18.
    • Problem 2.30.
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.

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: Monday
  • Homework Assignment for Monday of Sixth Week:
    • Exercise 2.2 (from Wednesday Week 5)

  • Reading Assignment for Monday of Sixth Week:
    • Read Sections 3.1 and 3.2.

  • Discussion Questions and New Material for Monday of Sixth Week:
    • 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.
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.
Week 6: Friday


Week 7: Monday

  • Homework Assignment for Monday of Seventh Week:
    • 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.

  • 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:
    • Read Section 4.1.

  • Discussion Questions and New Material for Wednesday of Seventh Week:
    • 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 (not in 2nd edition).
    • Exercise 4.6 (4.5 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).

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.