Computer Science 456/656: Automata and Formal Languages

Spring 1999

Assignments

This page will be updated frequently. Most recent update: April 28, 1999.

• Background. You will be assumed to know the contents of sections 1.1 through 1.4, pages 3-27 of your textbook.
• January 20, 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).
• Homework due. Assignment 1 will be due on Monday, February 1, in class.
• January 25, 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.
• No textbooks. Because the textbooks were not available in the bookstore before Monday January 25, the due date of Assignment 1 will be extended to Monday, February 1.
• January 25, 1999. The topics of today's lecture will include the concept of a machine accepting a language. We will introduce finite automata and possibly discuss regular languages. Read Chapter 3, pages 69-99 of your textbook.
• January 27, 1999. Today's lecture will continue of the topic of machines accepting languages. We will introduce finite automata and regular languages and regular expressions. Read Chapter 3, pages 69-99 of your textbook.
• February 1, 1999. Today's lecture will continue of the topic of machines accepting languages. We will introduce non-deterministic finite automata, and show that the class of languages they accept is also the class of regular languages. Thus, for finite automata, non-determinism does not increase their computational power. Read Chapter 4, pages 100-134 of your textbook.

  If time permits, we will begin some of the material in Chapter 5, pages 135-160 of your textbook.

• Homework due. Assignment 2 will be due on Monday, February 8, in class.
• February 3, 1999. Today's lecture will continue of the topic of regular languages and finite automata. We will show how to find a DFA equivalent to a given NFA, and also how to find the minimal DFA equivalent to a given DFA. We will introduce the pumping lemma, an important tool in the dicussion of regular languages. Be sure to finish reading Chapter 5 of your textbook.
• February 8, 1999. Today's lecture topic will be a continuation of the discussion of regular langauges. We shall attempt to cover Chapter 5 of your textbook (pages 135-160). The major topic will be the Pumping Lemma.
• Examination. We will have a short exam on February 10. The exam will cover material up to, and including, Chapter 5 in your textbook.

  As preparation for the examination, it might be wise to work a few more parts of problem 5.35 on page 159 of your textbook. (But do not hand them in.)

• February 17, 1999. Today's lecture topic will be a continuation of the discussion of context free languages. We shall attempt to cover Chapter 6 of your textbook, pages 163-197, but it is unlikely that we will finish that chapter today.
• Homework due. Assignment 3 will be due on Wednesday, February 24, in class.
• February 22, 1999. Today's lecture topic will be a continuation of the discussion of context free languages. We continue with Chapter 6 of your textbook, pages 163-197. We may be able to get to the Pumping Lemma today.
• February 24, 1999. Today's lecture topic will be pushdown automata (PDAs) and their connection with context free languages (Chapter 7 of your textbook, pages 198-236).
• March 1, 1999. Today's lecture topic will be continued discussion of pushdown automata.
• March 3, 1999. Today's lecture topic will be continued discussion of pushdown automata and context-free languages.
• Homework due. Assignment 4 will be due on Wednesday, March 3, in class.
• March 8, 1999. Today's lecture topic will be continued discussion of pushdown automata and context-free languages, with applications to parsing.
• March 10, 1999. Today's lecture topic will be continued discussion of pushdown automata and context-free languages, with continuation of the discussion of applications to parsing.
• March 15, 1999. Today's lecture will cover the Pumping Lemma for context-free languages. Please read Chapter 8 of your textbook, pages 237-254.
• Homework due. Assignment 5 will be due on Monday, March 15, in class.

  A shift-reduce parser in postscript also in html I apologize for the fact that the html file is not currently organized properly. However, all the relevant information is there: just click on the links marked "Exercise" to get all the information.

  Warning: there is at least one error in this file. Email notification of errors you detect are strongly encouraged.

• March 17, 1999. Today's lecture will cover remaining topics in your textbook, up through and including Chapter 8, in preparation for the examination on Monday.
• Examination. We will have a examination on March 22. The exam will cover material up to, and including, Chapter 8 in your textbook.
• March 24, 1999. Today we will begin the discussion of Turing machines. Please start by reading the first five sections of Chapter 9 of your textbook, pages 255-276.
• April 5, 1999. Today, we continue our discussion of Turing machines. We will explain the Church-Turing Thesis, and its relevance to the problem of decidability. Read Chapter 9 of your textbook, pages 255-293.
• April 7, 1999. We consider recursive and recursively enumerable languages. We show that a language is recursive if and only if it is decidable. We show that the universal language is not recursive, which is equivalant to saying that the halting problem (the problem of whether a given machine halts with a given input) is undecidable. Read Chapter 10 of your textbook, pages 294-310.
• Homework due. Assignment 6 will be due on Monday, April 19, in class.
• April 19, 1999. Today we will introduce the concept of a general grammar, also known as a phase-structure grammar or an unrestricted grammar. The main theorem is that the class of languages generated by these grammars is precisely the class of recursively enumerable languages, that is, those that are accepted by Turing Machines. There are other well-known classes of grammars which are historically significant, such as context-sensitive grammars, regular grammars, and linear grammars.

  Today, we will discuss reduction. You have used that word many times, casually, such as in the sentence, "I can solve the reachability problem by reducing it to breadth-first search." Clearly, a precise definition is needed, and we will, together, invent one!

• Homework due. Assignment 7 will be due on Monday, April 26, in class.
• April 26, 1999. In today's lecture, we will finally discuss the most amazing fact of all, namely that there exist undecidable problems, and in fact, problems that are very easily stated that are undecidable! (For an example, look at a very quick proof that the Pascal program halting problem is undecidable.
• April 28, 1999. In today's lecture, we will
• May 3, 1999. Dr. Kazem Taghva will give today's lecture. He will discuss recursive function theory. Be sure to read Chapter 13 of the textbook, pages 363-394.
• May 5, 1999. In today's lecture, we discuss complexity theory. In particular, we shall define the concept of NP-completeness.
• Homework. Work Assignment 8 by May 12, but do not turn it in.
• Final Examination. Our final examination is scheduled for 6:00 PM on Wednesday, May 12. The examination will be comprehensive.