## COMP272: Theory of Computation: Spring 1997

Syllabus

FINAL EXAM GRADES -- Posted May 23, 1997

NEW Grades so far (Quiz1 + Exam1 + Quiz2 + Exam2)

Answers for Quiz2

Announcement: The review session will take place on Saturday, 17 May,
from 3-4 PM in Room 2406.

### Lecture Notes

Introduction and overview
Set, relations, and functions (a review)
Languages and regular expressions
Empty Sets vs. Empty Strings (extra handout)
A First Example of A DFA
Finite Automata
The Fundamental Theorem
Properties of Regular Languages
The Pumping Theorem For Regular Languages
A Second Pumping Theorem For Regular Languages
Context-Free Languages: An Introduction
Pushdown Automata
More on Context-Free Languages
Introduction to Turing Machines
Combinations of Turing Machines
Extensions of Turing Machines
Universal Turing Machines
Uncomputability
Some Unsolvable Problems
### HomeWork Assignments

HomeWork 1: Due February 20, 1997
and
Solutions
HomeWork 2: Due February 27, 1997
and
Solutions
Homework 3: Due March 6, 1997. Problems 2.1.3 (a), (c),
2.2.2 (b) and 2.45 (a), (b), (d) from textbook.
Solutions
HomeWork 4: Due March 20, 1997
Solution: Part 1 and
Part 2
Homework 5: Due April 10, 1997. Problems 3.1.8 (a), (b), (c), (f),
3.2.1 and 3.2.2 from textbook.
Solutions (corrected version)
Homework 6: Due April 17, 1997. Problems 3.3.2 (a), (b),
3.5.1 (a), (b) and 3,5.2 (a), (b), (c) from textbook.
Solutions
Homework 7: Due May 8, 1997. Problems 4.1.3, 4.1.5, 4.2.3, 4.3.2,
and 4.4.7(a)
from textbook.
Solutions
### Old Exams from Fall 1996

Quiz1
Midterm
Quiz2
Exam2