EECS 4100 - Theory of Computation Course Syllabus
Credits/Contact Hours
3 credit hours & 160 minutes lecture contact hours per week.
Textbook
Michael Sipser, Introduction to the Theory of Computation, 3rd Ed., Cengage Learning,
ISBN: 9789-1-133-18779-0
Course Information
Examines formal models of automata and languages. Finite-
state automata, regular languages, pushdown automata, context- free languages, Turing
machines, decidability, reducibility, and P vs NP complexity classes.
Prerequisites: EECS 2510: Nonlinear Data Structures and EECS 2520: Discrete Structures
Elective or Required Course: Required.
Specific Goals - Student Learning Objectives (SLOs)
The students will be able to:
1. Devise a variety of simple proofs.
2. Define what a Regular Language is and construct a finite state machine for it.
3. Construct equivalent representations among Regular Languages, Regular Expressions,
and Regular Grammars.
4. Formulate a grammar defining the syntax of common programming languages.
5. Be able to formulate the equations for pushdown automaton.
6. Understand Turing Machines and the simple primitive mechanisms needed for all computation.
7. Understand recursive and recursively enumerable languages.
8. Identify the characteristics of problems for which no computational solution exists.
9. Understand the concepts of P vs. NP vs. NP-complete.
Specific Goals – Outcome 1: Supported by 1, 2, 4, 5, 7, 8, 9
EAC Crit. 3 Outcomes
Specific Goals – Outcome 1: Supported by SLOs 2, 4, 5, 9
CAC Crit. 3 Outcomes Outcome 6: Supported by SLOs 5 and 7
Topics
- DFA’s and regular expressions
- NFA’s and conversion to DFA
- Regular Expression to GNFA to NFA
- Pumping lemma for Regular Languages
- PDA and NPDA
- Context Free Grammars, Chomsky Normal Form, and Greibach Normal Form.
- Pumping Lemma for CFL, DK-Test, and LR Parsing
- Turing Machines
- Turing Machine Types – Recognizers, deciders, enumerators, and other equivalent machines.
- Decidability
- Reducibility
- Complexity
- Intractability
- Approximation Algorithms