Theory of Computation (under-grad course)
Instructor: Hossein Jowhari
TA: Abolfazl Falahati
Semester: Fall 2018 (97-1)
Time: SUN, TUE 3:30pm-5:00pm
Textbook: Introduction to the Theory of Computation. Michael Sipser. 3rd Edition.
Midterm: 6th Azar
Lectures :
- Introduction.
- Finite Automata. A few examples.
- Finite Automata. Regular Languages. Formal definitions.
- NFA. Examples
- Every NFA has an equivalent DFA
- Regular Expressions pdf
- Pumping Lemma
- Solutions for selected problems
- Solutions for selected problems
- Grammars and Context Free languages
- Grammars and Context Free languages
- Chomsky Normal Form
- Push-down automata
- Push-down automata
- Turing Machines I
- Turing Machines II, Turing Recognizable, Turing Decidable
- Nondeterministic Turing Machine
Homeworks :