CS 373: Introduction to Theory of Computation

CS 373: Introduction to Theory of Computation

A collection of class notes used in teaching CS 373 (Theory of Computation), in the Computer Science department in University of Illinois at Urbana-Champaign.

Publication date: 18 May 2009

ISBN-10: n/a

ISBN-13: n/a

Paperback: 345 pages

Views: 2,350

Type: Lecture Notes

Publisher: n/a

License: Creative Commons Attribution-NonCommercial 3.0 Unported

Post time: 20 Oct 2016 04:00:00

CS 373: Introduction to Theory of Computation

CS 373: Introduction to Theory of Computation A collection of class notes used in teaching CS 373 (Theory of Computation), in the Computer Science department in University of Illinois at Urbana-Champaign.
Tag(s): Theory of Computation
Publication date: 18 May 2009
ISBN-10: n/a
ISBN-13: n/a
Paperback: 345 pages
Views: 2,350
Document Type: Lecture Notes
Publisher: n/a
License: Creative Commons Attribution-NonCommercial 3.0 Unported
Post time: 20 Oct 2016 04:00:00
Summary/Excerpts of (and not a substitute for) the Creative Commons Attribution-NonCommercial 3.0 Unported:
You are free to:

Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click here to read the full license.
Note:

More resources (including LaTEX source of the notes) are available here.

Excerpts from the Preface:
Har-Peled wrote: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. 




About The Author(s)


Margaret M. Fleck is a Research Associate Professor in the Department of Computer Science, University of Illinois, Urbana-Champaign. Her research interests include computational linguistics, computer vision, and programming language tools to support language and vision research. Right now, she's working on unsupervised algorithms that learn word boundaries from transcribed speech.

Margaret M. Fleck

Margaret M. Fleck is a Research Associate Professor in the Department of Computer Science, University of Illinois, Urbana-Champaign. Her research interests include computational linguistics, computer vision, and programming language tools to support language and vision research. Right now, she's working on unsupervised algorithms that learn word boundaries from transcribed speech.


Sariel Har-Peled is a Professor in the Department of Computer Science at University of Illinois at Urbana-Champaign. His main field of research is Computational Geometry, and he is also interested in clustering and learning.

Sariel Har-Peled

Sariel Har-Peled is a Professor in the Department of Computer Science at University of Illinois at Urbana-Champaign. His main field of research is Computational Geometry, and he is also interested in clustering and learning.


Book Categories
Sponsors
Icons8, a free icon pack