- Visualization of Automata
- JFLAP is software, for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems.
- Theory of Computation (sllides), Tyng-Ruey Chuang, 2014.
- Theory of Computation (sllides), Professor Harry Porter, Winter 2016.
Theory of Computation
Spring 2017, Shahid Beheshti University
- Michael Sipser (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
- John Martin, Introduction to Languages and the Theory of Computation, 4th Ed. Feb 2, 2010.
- Hopcroft, John E. and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley.
- Alan Turing (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. IEEE. 2 (42): 230–265.
- Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications.
- 35% - Midterm Exam (9 May 2017), chapters 3,4
- 65% - Final Exam
- (up to) 10% - Projects (Web Development, Contents, Design, Problem Solving)
The Church–Turing Thesis (Chp. 3)
-Variants of Turing Machines
-The Definition of Algorithm
Decidability (Chp. 4)
Reducibility (Chp. 5)
-Undecidable Problems from Language Theory
-A Simple Undecidable Problem
Time Complexity (Chp. 7)
- The Class P
- The Class NP
- Additional NP-complete Problems
Space Complexity (Chp. 8)
- Savitch’s Theorem
- The Class PSPACE
(c) 2017 Meysam Madani 2017