Finite automata and regular languages; pushdown automata and context-free languages; Turing machines and recursively enumerable sets; linear-bounded automata and context-sensitive languages; computability and the halting problem; undecidable problems; recursive functions; Chomsky hierarchy; computational complexity. Course Information: Same as MATH 475. 3 undergraduate hours. 3 or 4 graduate hours. Prerequisite: CS 374.
Automata Theory:
Recursion Theory:
Complexity Theory:
(exact topics subject to change)
Announcements are made in lecture and/or on our Piazza forum. Information about exams can be found here. You are encouraged to use Piazza to discuss concepts, homework problems, and the like. However, you may not post solutions to graded problems (e.g. exams, homeworks) that folks may still be working on. Even after the standard deadline, some of your classmates may still be working due to extensions. If you aren't sure whether it's appropriate to post something, consult the course staff.
We will be using
To sign up for CS 475 on piazza, you will need to use your illinois.edu (netID) email. If you have some reason why you don't want piazza to know your U. Illinois email, contact an instructor to be added under an alternate email address.
The required textbook for this course is Introduction to the Theory of Computation (3rd edition) by Michael Sipser.