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鈥檚 and regular expressions听
- NFA鈥檚 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听