Regular languages.
Problem set 2:
Construct the following NFA that accepts strings that end in 00.
Use the proof of the reduction of a NFA to a DFA to construct the DFA for this language.
Sipser 1.31, 1.36, 1.37, 1.38, 1.40, and 1.45.
Regular expressions. Do these problems and bring your solutions to the workshop:
Exercises 1.18, 1.28, 1.21 (b), 1.24 (a-d), 1.25, 1.26 (for T1 only), 1.27.
(Andrew Reinders teaches)
See new readings to outline, listed on readings page.
Work on these problems over the weekend and bring your solutions to class Tuesday: 1.49, 1.54.
Optional makeup Quiz 2: complete and bring to class Tuesday.
For workshop Wednesday, work on these exercises and bring your solutions to workshop: 2.4bcef, 2.5bcef, 2.6b, 2.9, 2.11, 2.27.
More on context free languages. Work on these exercises and bring your solutions to workshop Wednesday:
- Extend the grammar in exercise 2.1 to include unary - (negation) and binary - (minus).
- Convert that grammar to a PDA using the procedure given in Theorem 2.20.
- Convert the following PDA to a grammar using the procedure given in Theorem 2.20:
- Problem 2.22. Hint: Create a PDA that "guesses" the position of the first mismatch.
Finished context free languages.
Make-up Quiz 3. Turn this in on class on Tuesday 28 Feb. You may use textbook and other academic sources, but you should not search for solutions to the specific problems or collaborate.
Readings on Chapter 3 are due Sunday midnight.
Study and/or solve following problems to prepare for class Tuesday and for the workshop Wednesday:
- Example 2.36
- Example 2.38
- We saw that regular languages are closed under intersection. Use the result from Example 2.36 to prove that context-free languages are not closed under intersection. Explain why together with the fact that context-free languages are closed under union means that context-free languages are not closed under complement.
- We showed the solution to problem 2.22 in the last class. Study your notes so that you understand how and why this solution works:
0. Push $ on the stack.
1. Read next input symbol and push 1 on the stack.
2. Nondeterministically jump to either 1 or 3.
3. Record the current input symbol in the finite control (i.e. by going to a particular state).
4. Read input symbols until # is read.
5. Read the next symbol, and pop the stack.
6. If stack is empty ($ is not on top), then go to 7, else go to 5.
7. Accept if the current input symbol isn’t a, (i.e., go to accept state, where the accept state loops reading y until input is all gone), otherwise reject.Next, come up a PDA that shows the following language is context-free: L = { x#y | x,yt in {a,b,c}* such that some pair of letters "a" and "b" (in that order) in x are separated by the same distance as are a pair of letters "a" and "b" in y }. For example, L contains the string cabccbac#ccacabb because the first half contains and "a" and "b" separated by 3 characters, as does the second half. However, L does not contain the string caccbcb#bacbccacb.
Finish Pumping Lemma for CFL.
In class: Problem 2.31.
Workshop this week:
- Finish any of the problems listed above that we did not complete in class.
- Problem 2.18.
- Problem 2.31.
- If time: Problem 2.43
Ch 3: Church-Turing Thesis
For class Tuesday Mar 6 class and workshop Wed Mar 7:
- Modify Example 3.11 so that the TM computes i / j = k using integer arithmetic (rounding down, so 3 / 2 = 1).
- Modify the example again so it computes i mod j = k.
- Problems 3.15 and 3.16.
For class Thursday Mar 8, prepare by outlining Chapter 4 section 1 (pages 165 - 172). You will not turn in the outlines yet, but you should have them done.
Quiz 4: Pumping Lemma and PDAs. The questions will be similar to the problems listed for Feb 23 and Feb 28 (excluding 2.43).
Ch 3: Church-Turing Thesis
Ch 4: Decidability (Sec 4.1)
Read and outline rest of Chapter 4. The turn-in deadline (this time only) is NOON TUESDAY (March 20) rather than Sunday night. See also the problems for this week.
Ch 4: Decidability (Sec 4.2)
Class today: Proof that the Halting Problem is undecidable
Problems for workshop Wednesday: 4.3, 4.5, 4.9 (answer in book), 4.10, 4.6, 4.7, 4.28.
Special reading assignment: read Section 5.1 to the end of Theorem 5.4 (pages 187-192). Do not turn in yet.
Ch 5: Reducibility
Class today: Theorems 5.1, 5.2, 5.3, 5.4
Reading assignment due Sunday night: outline of Section 5.1 and 5.3 (skip section 5.2).
Ch 5: Reducibility
Class today: Sec. 5.3. and problems 5.28 (Rice's Theorem). We will start working on the following problems and finish them in workshop: 5.9, 5.13, 5.16 (busy beaver), 5.25, 5.30.
Make-up Quiz 4 handed out. Due at start of class Tuesday April 3.
Midterm (Automata and Decidability)
There will be six problems covering the following topics:
- Converting a NFA to a DFA.
- Using the pumping lemma for regular languages to show a language is not regular.
- Proving that a language is regular by constructing a PDA or a CFG.
- Using the pumping lemma for context free languages to prove that a language is not context free.
- Showing that a language is decidable by constructing a Turing machine that always halts that decides it.
- Using a mapping reduction to show that a language is undecidable by reducing the decision problem to the halting problem.
Reading assignment due *Monday* night at midnight: Outline Chapter 7.1 - 7.4. Although this is fairly long, you already know much of your material, so your notes can be brief. The details of the proof of the Cook-Levin are complicated, so at this point just try to grasp the high-level idea: you can revise your notes on this proof for the next set of outlines.
Ch 7: Time Complexity
Make-up Quiz 4 due.
Ch 7: Time Complexity - problems 7.24, 7.26, 7.29, 7.36, 7.42
(Andrew Reinders runs class)
Make-up Quiz 4 returned.
Class Cancelled
Reading outlines due Sunday: Chapter 8, Sections 8.1-8.3
Quiz 5 (Time Complexity)
Space Complexity (Sec 8.1-8.3: outlines due midnight Monday April 16)
Space complexity classes; Savitch's theorem; Quantified Boolean Formulas
Space Complexity
PSPACE-completeness; Games
Make-up Quiz 5. Due in class Tuesday Apr 24.
My notes on Savitch's Theorem, PSPACE-Completeness, and Games.
Space Complexity (Definition of an oracle, Sec 9.2 up to page 349, and Section 10.3 Alternating Machines, pages 380-386: outline due midnight Sunday April 22)
Alternating machines; Polynomial Hierarchy
Space Complexity & the Polynomial TIme Hieararchy
My notes on the polynomial time hierarchy.
Problem set on polynomial hierarchy. You will complete and turn in for a grade in class on Tue May 6. (This replaces a quiz.)