Computer Science 456/656: Automata and Formal Languages

Spring 2002

Assignments

This page will be updated frequently. Most recent update: December 15, 2002.

• Background. I expect you to know the material in Sections 1.1 through 1.4 of your textbook (pages 1-28). That material is very important for the course, and will appear in tests, but I do not plan to lecture on it.
• Tuesday, August 27, 2002.
  Today we will discuss Sections 1.5, 1.6, 1.7, 2.1, and 2.2, that is, up to page 55 of your textbook.
• Thursday, August 29, 2002.
  The major topic of discussion today will be the proof of Theorem 2.32 on page 79 of your textbook. In order to discuss that result, we will need to introduce non-deterministic finite automata.
• Tuesday, September 3, 2002.
  Assignment 1 is due today.
  Today we will prove that every NFA is equivalent to some DFA. (Theorem 2.12 on page 64 of your textbook.)
  We will also discuss "epsilon" transitions for an NFA.
  If there is time today, we will discuss regular expressions.
  We will postpone the discussion of minimizing a DFA (Section 4.4.3 of your textbook) until later.
• Thursday, September 5, 2002.
  Assignment 2 is due today.
• Tuesday, September 10, 2002.
  Today we will review some of the homework assignments.
  We will also show how to minimize a DFA.
• Thursday, September 12, 2002.
  Today we will discuss homomomorphisms and boolean operators on regular languages. Reaeach Section 4.1 of your textbook.
  We will also introduce the pumping lemma for regular languages. Read Section 4.2 of your textbook.
• Tuesday, September 17, 2002.
  Assignment 3 is due today.
  Today we will introduce context-free grammars.
• Thursday, September 19, 2002.
  Room Change. Due to a College of Engineering faculty meeting in TBE A107, class today will be held in WHI 105.
  Assignment 4 is due today.
  Today we will continue our discussion of context-free grammars.
• Tuesday, September 24, 2002.
  Today we will continue our discussion of context-free grammars.
• Thursday, September 26, 2002.
  Assignment 5 is due today.
  Examination today.
• Tuesday, October 1, 2002.
  Today I will hand back the graded exam, and go over the problems.
  If time permits, we will introduce push-down automata.
• Thursday, October 3, 2002.
  We will continue our discussion of push-down automata.
• Tuesday, October 8, 2002.
  We will continue our discussion of push-down automata.
  Assignment 6 is due today.
• Thursday, October 10, 2002.
  Today we will discuss properties of context-free languages, including the pumping lemma and closure properties (which are introduced in Section 7.3 of your textbook).
• Tuesday, October 15, 2002.
  Assignment 7 is due today.
  Today we will go over the CYK algorithm in detail. After that, we will the most important part of the course, the discussion of what can and cannot be computed by a machine. We begin the topic with an informal discussion decidability, and then give a definition of Turing machine. If no Turing machine can decide a problem, then no machine can decide that problem, regardless of how large and complex that machine is. An example of an undecidable problem is, given a certain program P, and given a certain input file w, does P ever halt with input w? This is called the halting problem.
  You might think that deciding the halting problem is easy ... "Just run the program." If it halts, the answer is yes. But if it doesn't halt, you never get the "no" answer, because it just keeps running and you don't know whether it will halt at some future time. In certain cases, you can prove it never halts. But the problem can only be said to be decidable if you can decide whether it halts in all cases. If the halting problem were decidable, that would mean that there would exist a machine M such that, for any program P and input file w you could insert Pw into M as input, and M would always halt and give, as output, the answer to the problem. We shall prove that no such M can exist.
• Thursday, October 17, 2002.
  Today we shall continue the discussion of computability. We shall give a formal description of a Turing machine.
• Tuesday, October 22, 2002.
  Assignment 8 is due today.
  Today we will continue the discussion of Turing machines, with emphasis on the Church Turing Thesis.
• Thursday, October 24, 2002.
  I will be somewhat late for my office hour today.
• Tuesday, October 29, 2002.
  Today we shall discuss the proof of undecidability of certain languages. This is a big topic, and will take several lectures.
• Thursday, October 31, 2002.
  Office hour is at a different time today.
  We shall continue the discussion of the last lecture.
• Tuesday, November 5, 2002.
  Office hour is at a different time today.
  Examination in class today. A partial summary of the material that might be on the examination.
• Thursday, November 7, 2002.
  Office hour is at a different time today.
  I will hand back the test today.
  Today we will begin the proof of the undecidability of grammar equivalence, the hardest theorem of this course, in my opinion.
  Instead of presenting it myself in one or two lectures, I will let you do most of the work, in the form of homework assignments. Here's the first one:
  Assignment 9 is due Tuesday, November 12. Answers to Assignment 9.
• Tuesday, November 12, 2002.
  Answers to Assignment 9.
  The first part of Assignment 10 is due Thursday, November 14.
• Thursday, November 14, 2002.
  Office hour will be canceled today. I will, be in class tonight, though.
• Tuesday, November 19, 2002.
  Office hour is at a different time today.
  The second part of Assignment 10 is due Tuesday, November 19.
  We will begin working on the remaining major topics of the semester.
• Thursday, November 21, 2002.
  Cartoons referring to NP-completeness.
• Tuesday, November 26, 2002.
  Office hour is at a different time today.
  Assignment 11 is due Tuesday, November 26.
  Boolean satisfiability is NP-complete.
• Thursday, November 28, 2002.
  Thanksgiving Recess.
• Tuesday, December 3, 2002.
  Today we will review some proofs like those that might appear on the final exam.
• Thursday, December 5, 2002.
• Tuesday, December 10, 2002.
  Office hour today, 9:30 to 11:00.
  Final Examination, 6:00 PM.
  Review for final.
• Monday, December 16, 2002.
  Final course grades are now available.