Computer Science 456/656: Automata and Formal Languages

Fall 1999

Assignments

This page will be updated frequently. Most recent update: December 20, 1999.

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.
• Tuesday September 7, 1999. The topics of today's lecture will be languages (Section 1.5 of your textbook, pages 27-35) and proof techniques, including induction, diagonalization, and the pigeonhole principle (Chapter 2 of your textbook, pages 36-70).
  We will discuss the standard operations on languages: union, concatenation, and Kleene closure.
• Thursday September 9, 1999. The topics of today's lecture will be proof techniques, including induction, diagonalization, and the pigeonhole principle (Chapter 2 of your textbook, pages 36-70).
  We will discuss the relationship between problems (such as the knapsack problem, the traveling salesman problem, or the addition problem) and what it means for a problem to be hard.
  We will introduce the concept of regular languages. We will introduce regular expressions and finite automata.
• Homework due. Assignment 1 will be due on Tuesday, September 14, in class.
• Tuesday September 14, 1999. We will continue the discussion of regular languages. We will continue the discussion of proof techniques and regular expressions, and introduce finite automata.
• Thursday September 16, 1999. Today, we will continue the discussion of regular languages and automata, and introduce non-deterministic finite automata, NFA for short. You should have read up to page 107 in your textbook by today.
• Homework due. Assignment 2 will be due on Tuesday, September 21, in class.
• Tuesday September 21, 1999. We will continue the discussion of regular languages and finite automata. We give the proof that every NFA is equivalent to some DFA.
• Thursday September 23, 1999. Today, we will continue the discussion of regular languages and automata. We will give the proof that the language described by any regular expression is accepted by some NFA.
• Tuesday September 28, 1999. We will continue the discussion of regular languages and finite automata. We will introduce the Pumping Lemma and use it to prove that some languages are not regular.
• Thursday September 30, 1999. We will continue the discussion of the Pumping Lemma and how to use it to prove that some languages are not regular.
• Homework due. Assignment 3 will be due on Tuesday, October 5, in class.
• Tuesday October 5, 1999. We will continue the discussion of the Pumping Lemma and how to use it to prove that some languages are not regular.
  We will clarify some confusion on the Pumping Lemma.
  We will introduce the concept of homomorphisms of languages, and state some more theorems about regular languages.
• Thursday October 7, 1999. It is time to move beyond regular languages. Today we shall introduce the next major topic, context-free languages and push-down automata.
• Tuesday October 12, 1999. We will continue to discuss context-free languagues, and discuss how to work some of the homework problems in Assignment 4.
• Homework due. Assignment 4 will be due on Thursday, October 14, in class.
• Out of town. Beginning at 10:20 AM, I will be out of town October 19. There will be no office hours. The examination will be proctored.
  Examination. We will have an examination on October 19. This exam will cover regular languages, as well as the beginning material on context-free languages covered up to the time of the exam.
• Tuesday October 25, 1999. We will continue to discuss context-free languagues, and the relation to push-down automata (PDA's).
• Thursday October 27, 1999. We will introduce DPDA's and parsers.
• Tuesday November 2, 1999. We will continue to discuss DPDA's and parsers.
  We will discuss Assignment 5.
  We will introduce the pumping lemma for context-free languages.
  If time permits, we will discuss bottom-up parsing in detail.
• Homework due. Assignment 5 is due Thursday November 4, 1999.
• Thursday November 4, 1999. We will continue the discussion of bottom-up parsing.
  A bottom-up parser.
• Tuesday November 9, 1999. Although there is still homework due concerning parsers, we must move on.
  We will introduce Turing machines and the Church-Turing Thesis. This is the statement that Turing machines are, as a class, capable of doing any computation that can be done by any machine. This means, in particular, that any Truth that can be known by reason alone can be proved by a Turing machine.
  Functions that can be computed by a machine are called recursive functions. Most likely, all of the functions you have ever heard of are recursive.
  We shall, later, prove the existence of Truths that cannot be proved by any Turing machine. This means that there are Truths that can never be known by reason.
  Similarly, we shall prove the existence of functions which are not recursive. One classic example is the "Busy Beaver" function.
  There are some who claim that if a statement cannot be known by reason, it cannot be said to be true. This claim is false, and one of the goals of this course is to convince you of that fact.
• Thursday November 11, 1999. Veterans' Day holiday. Originating as a holiday honoring the dead of the Great War (now called the First World War), today we honor all those who have served in the Armed Forces.
  Although there will be no lecture, I will be hard at work, logged on from somewhere, reading your email and zwrite questions about the lectures and homework, and sending sending you helpful messages. Please use this long weekend wisely to get ahead on the homework.
  One of the things I will be doing today is putting the Spring 2000 Course Schedule up on the web. Feel free to interrupt me with email and zwrite concerning the course, however.
• Homework due. Assignment 6 is due Tuesday November 16, 1999.
• Homework due. Assignment 7 is due Thursday November 18, 1999. Note change in assignment. Two problems will be due next Tuesday instead, as Assignment 8.
• Homework due. Assignment 8 is due Tuesday November 23, 1999.
• Assignment 9 will not be collected, but be sure to work it by Tuesday November 30, 1999.
• Thursday December 2, 1999. Today we will introduce the concept of NP-completeness.
• Assignment 10 will not be collected, but be sure to work it by Tuesday December 7, 1999.
• Tuesday December 7, 1999. Today we will continue the discussion of NP-completeness, and indicate why Boolean Satisfiability is NP-complete.
• Thursday December 9, 1999. Today we will introduce general grammars. A language can be generated by a general grammar if and only if it is recursively enumerable. General grammars are also known as phase structure grammars or unrestricted grammars.
• Final Examination. Our final examination is scheduled for 6:00 PM on Tuesday, December 14. The examination will be comprehensive.
• Final Grades are not yet ready. This line will be changed when they are ready.