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.
- Reading Assignment for Wednesday of First Week:
- Read Chapter 0. (Everything after Section 0.1 should be review.)
- Read Section 1.1.
- An Example-Based Introduciton to Finite-State Machines
- 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}.
- {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.)
- Give state diagrams of deterministic finite automata recognizing the
following languages. In all cases the alphabet is {0,1}.
- 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:
- 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.
- 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.
- Exercise 1.14:
- 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}.
- Exercise 1.7 b.
- Exercise 1.7 e.
- Exercise 1.10 b.
- Exercise 1.10 c.
- 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.
- Give NFAs with the specified number of states recognizing
each
of the following languages.
In all cases the alphabet is {0,1}.
- 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.)- {w | w contains at least three 1s}.
- {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}.
- 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.
- Give regular expressions generating the following languages.
In all cases the alphabet is {0,1}.
- 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:
- Be sure you've read Section 1.4.
- Watch the video What is the Pumping Lemma
- Watcht the video Nonregular languages: How to use the Pumping Lemma
- 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:
- 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.
Discuss each of the following:
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.
- 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.
- 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}.
- Convert the following grammar into Chomsky Normal Form:
-
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.
- 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.
- Small group meetings
- TBD
- 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
- 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.
- 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.
- 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.
- Small group meetings to go over Turing machine examples.
- Reading Assignment for Friday of Sixth Week:
- 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:
- Discussion Questions for Friday of Sixth Week:
- NO CLASS MEETING
- 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
- 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.
- 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.
- 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.
- 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.