Theory of Computation

Student Learning Outcomes, Goals, Objectives:

In this class we explore the most fundamental question in computer science: What does it mean to compute something? This includes exploring issues such as processes/models that can mechanize computations, problems that can and cannot be solved with different models of computation, and fundamental limitations that restrict what problems can be solved computationally. While the focus of an algorithms class is on how fast problems can be solved by modern computers, this class digs deeper into the fundamental question of what problems are possible to solve in various computational models. The approach in this class is formal, using precise mathematical models and a significant amount of formal reasoning and mathematical proofs.

Students successfully completing this course will be able to:

• Understand the basic theoretical models of computability: deterministic and nondeterministic finite automata, pushdown automata, and variants of Turing machines.

• Design finite automata corresponding to given regular sets, and describe the regular set recognized by a given finite automaton. Do the same with pushdown automata and context free languages, and with Turing machines and recursively enumerable sets.

• Comprehend and apply several algorithms such as: the subset construction to transform a nondeterministic finite automaton into a deterministic one; the DFA state minimization algorithm to minimize the number of states in a deterministic finite automaton; and conversion algorithms from regular expressions to finite automata and vice-versa.

• Understand limitations of finite automata (respectively, pushdown automata) and prove that some sets are not regular (respectively, context-free) by using the pumping lemma for regular languages (respectively, context-free languages).

• Simulate CFGs by NPDAs and vice-versa, that is, convert a given context-free grammar to an equivalent nondeterministic pushdown automaton, and convert a nondeterministic pushdown automaton to an equivalent context-free grammar.

• Apply algorithms to transform context-free grammars into normal forms such as the Chomsky normal forms.

• Design and analyze Turing machines to recognize and decide formal languages, and use them to characterize the limits of algorithmic computation.

• Prove that some problems are decidable or undecidable using techniques such as diagonalization and reduction.

Course Grading Information:

Activity/Performance Measure	Percentage/Points
Assignments	40%
Mid-Term 1	15%
Mid-Term 2	15%
Final Exam	20%
Attendance	10%

Grading Scale

Percentage	Letter Grade
94-100	A
90-93	A-
87-89	B+
84-86	B
80-83	B-
77-79	C+
74-76	C
70-73	C-
67-69	D+
64-66	D
60-63	D-
<59	F

Attendance/Participation:

Attendance is mandatory for all class meetings. If a student is unable to attend an in-person class, they must inform the instructor in advance by providing a valid reason for their absence. This communication should be done through email and must be sent before the class session begins. Failure to notify the instructor prior to the start of class will result in the student losing credit for that absence. It should be noted that attendance records may be taken either at the beginning or the end of the class. Students are advised to ensure their presence throughout the session to avoid any discrepancies in the attendance record.

There will be in-class short-quizzes or problem solving for bonus points.

Course Materials Purchased by the Students:

The instructor will provide lecture notes which are mostly based on the following reference book: Michael Sipser, Introduction to Theory of Computation, 3rd edition, Cengage Learning, 2013. ISBN-13: 978-1133187790