CS 373: Introduction to Theory of Computation

This manuscript is a collection of class notes used in teaching CS 373 (Theory of Computation), in the spring of 2009, in the Computer Science department in UIUC. The instructors were Sariel Har-Peled and Madhusudan Parthasarathy. They are based on older class notes – see second preface for details.

This class notes diverse from previous semesters in two main points:

(A) Regular languages pumping lemma. Although we still taught the pumping lemma for regular languages, we did not expected the students to use it to proving languages are not regular. Instead, we provided direct proofs that shoes that any automaton for these languages would require infinite number of states. This leads to much simpler proofs than using the pumping lemma, and it seems the students find them easier to understand. Naturally, we are not the first to come up with this idea, it is sometimes referred to as the “technique of many states”. 

The main problem with the pumping lemma is the large number of quantifiers involved in stating it. They seem to make it harder for the student to use it. 

(B) Recursive automatas. Instead of teaching PDAs, we used an alternative machine model of Recursive automata (RA) for context-free languages. RAs are PDAs that do not manipulate the stack directly, but only through the calling stack. For a discussion of this issue, see Chapter 20 (page 127). 

This lead to various changes later in the course. In particular, the fact that the intersect of CFL language and a regular language is still CFL, is proven directly on the grammar. Similarly, the proof that deciding if a grammar generates all words is undecidable now follows by a simpler but different proof, see relevant portion for details. 

In particular, the alternative proof uses the fact that given two configurations of a TM written on top of each other, then a DFA can verify that the top configuration yields the bottom configuration. This is a cute observation that seems to be worthy of describing in class, and it leads naturally into the Cool-Levin theorem proof.