This is suggested reading for the weeks listed.
The lectures will start with section 1.7 on page 42. However, we will be using the material in sections 1.1 to 1.6.
In the lectures we will cover deterministic and nondeterministic finite automata and their equivalence. We also return to regular expressions to show they are equivalent to finite automata.
We still have to show the equivalence of regular expression and finite automata. After that we will examine non-regular languages and algorithms for deciding properties of finite automata.
We will start on context-free grammars late this week. You can read ahead.
You may read ahead to see the connection between pushdown automata and context-free grammars.
We will cover techniques to show languages are not context-free. We will look at a few algorithms about context free grammars. We will explore some about deterministic context-free languages. 11/23/98 - Chapter 4, pages 179 to 221
This is the first 4 sections of chapter 4. We want to cover the basics of Turing machines including multiple tape and random access memory simulations. 11/30/98 - Chapter 5, pages 245 to 261
This is the first 5 sections of chapter 5. Here we cover the Church-Turing thesis, universal Turning machine, undecidability of the halting problem, and undecidable problems about context-free grammars.