Computer Science 456/656: Automata and Formal Languages

Spring 2000

Assignments

This page will be updated frequently. Most recent update: May 14, 2000.

Final Grades are Available Now.
Turing Machine Emulation

• Background. You will be assumed to know the contents of sections 1.1 through 1.4, pages 3-27 of your textbook.
• Wednesday January 19, 2000. Today we give overview of the whole of the course.
  We start by introducing the concepts of alphabet and language.
• Monday January 24, 2000. The topics of today's lecture will be languages (Section 1.5 of your textbook, pages 27-35) and proof techniques, including proof by contradiction, induction, diagonalization, and the pigeonhole principle (Chapter 2 of your textbook, pages 36-70).
• Wednesday January 26, 2000. The topics of today's lecture will be languages in general, and regular languages in particular.
  We will discuss the standard operations on languages: union, concatenation, and Kleene closure.
  If time, we will introduce the concept of a Finite State Automaton.
• Homework due. Assignment 1 will be due on Monday, January 31, in class.
• Monday January 31, 2000.
• Wednesday February 2, 2000.
• Monday February 7, 2000. The topics of today's lecture will be finding a DFA equivalent to an NFA, and constructing a minimal DFA.
• Wednesday February 9, 2000. The topics of today's lecture will be finding an NFA which accepts the language described by a regular expression.
  If there is time, we will introduce the Pumping Lemma.
• Homework due. Assignment 2 will be due on Wednesday, February 16, in class.
• Examination. There will be an examination on Wednesday, February 16, in class. It will cover material up through, and including, Chapter 5 in your textbook.
• Wednesday February 23, 2000. Today we will introduce context-free languages. This important class of languages will occupy a substantial fraction of the remaining course time, and is covered in our textbook in Part III, pages 161-253.
• Monday February 28, 2000. I will not have regular office hours today because of a faculty committee meeting at 2:00. But I will be on campus most of the day.
• Homework due. Assignment 3 will be due on Wednesday, March 1, in class.
• Homework due. Assignment 4 will be due on Wednesday, March 8, in class.
• Wednesday March 13, 2000. Today we will discuss the Pumping Lemma for context-free languages, and use it to show that certain languages are not context-free.
  Completion of lecture interrupted by fire alarm.
• Monday March 20, 2000. There will be a shortened office hour today, as I will be meeting Dr. Ronald Sack, Candidate for Dean of Engineering, at 3:00 pm today. There will be class as usual, however.
  Today in lecture we will continue the disucssion of push-down automata, otherwise known as PDAs.
• Wednesday March 22, 2000. Today we will introduce two kinds of parsers, bottom-up parsers and top-down parsers. Each uses one stack and reads the input in one pass.
  These parsers basically fit into the PDA model, with some extra features.
  Bottom-up parsers are the model for parsers frequently used by compilers.
• Examination. There will be an examination on Wednesday, March 29, in class. It will cover material up through, and including, Chapter 8 in your textbook.
• Monday April 3, 2000. Today we will introduce Turing Machines.
  The rest of the course will be taken up with fundamental questions such as decidability, computability, and time complexity.
• Wednesday April 5, 2000. Today we will discuss the Church-Turing thesis.
• Monday April 10, 2000. Today we will give some simple examples of how Turing machines compute functions and accept languages.
  We will also show how a TM can be used to emulate an NTM.
  We will show how a 2-DPDA can emulate a TM, and also how a Pascal machine can emulate a TM.
• Wednesday April 12, 2000. Today we will discuss Universal Turing machines.
• Homework due. Assignment 5 will be due on Monday, April 17, in class.
• Lab update. The lab is made tolerable at this time (Wednesday, April 12) by virtue of fans. We are still awaiting action to fix the normal cooling system.
  The cooling system in my office is partially fixed, making it possible for me to work here, at least for now. They are giving us a three-week timetable for a complete fix.
• Monday April 17, 2000. Today we will continue the discussion of recursive and recursively enumerable languages.
• Wednesday April 19, 2000. Today we will finish the discussion of recursive and recursively enumerable languages.
  We will discuss the concept of reduction and show how to use reduction to prove that many problems are undecidable.
  If time permits, I shall introduce the famous "Does P=NP?" problem and begin to explain what the question means in formal terms.
• Monday April 24, 2000. Today we shall give a formal definition of the language classes P-TIME and NP-TIME. (These are usally called "P" and "NP" for short.)
  It is known that P is a subclass of NP, but it is not known whether there is any language which is NP but not P.
  Using the concept of reduction, we shall introduce the concept of an NP-complete language.
  There are literally thousands of NP-complete languages (problems) known. If any one of them is P, then P=NP.
• Wednesday April 26, 2000. We shall prove that the Boolean Satisfiability problem is NP-complete.
  If time permits, we shall show how to prove that a many other languages (problems) are also NP-complete, using reduction.
• Homework due. Assignment 6 will be due on Wednesday, April 26, in class.
• Monday May 1, 2000. and Wednesday May 3, 2000. Some possible topics this week:
  • Practical importance of the P=NP question.
  • Practical importance of undecidability.
  • Undecidability of the program grader problem.
  • Undecidability of the grammar equivalence problem.
  • Factoring: no one is sure how hard it is, and security of encryption is at stake!
  • Randomized computing.
  • Alternating Turing Machines.
  • Quantum Computers.
• Wednesday May 10, 2000. Final Examination at 6:00 PM. Two hours.