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**: 6,403

**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

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.

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.

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

Note:

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

Excerpts from the Preface:

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.

Tweet

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.

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

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors