CS 385 Theory of Computation
Total Credits: 3 cr
Course Coordinator: Terry Soule
URL: http://www2.cs.uidaho.edu/~cs385
Current Catalog Description: See Math 385. Mathematical models of
computation, including finite automata and Turing machines. Prereq: perm.
Textbook: P. Linz, An Introduction to Formal Languages and Automata,
3rd Edition, Jones and Bartlett, 2001 or similar text.
References: Online notes and handouts, including FSA simulators.
Course Goals: Introduce the student to the need for, and the working
of, mathematical proofs. Develop facility for the concepts, notations, and techniques
of the theories of automata, formal languages and Turing machines.
Prerequisites by Topic:
- Trees, graphs, worst case analysis, recursion (CS 121)
- Induction, counting (Math 175)
- Series, set theory (Math 176)
Major Topics Covered in the Course: : (duration) (CC2001 BOK reference)
- Language Theory (AL7)
- Recursive definitions ( 2 hours)
- Regular expressions and languages ( 2 hours)
- Finite automata ( 2 hours)
- Kleene's theorem ( 1 hour)
- Myhill-Nerode theorem ( 1 hour)
- Nondeterminism ( 4 hours)
- Finite automata with output ( 2 hours)
- Nonregular languages ( 4 hours)
- Pushdown automata ( 2 hours)
- Contex-free grammars ( 2 hours)
- Chomsky normal form ( 2 hours)
- Non-context-free grammars and languages ( 3 hours)
- Parsing algorithms ( 1 hour)
- Computability Theory (AL5)
- Turing machines ( 3 hours)
- The Halting problem ( 1 hour)
- Rice's theorem ( 1 hour)
- Complexity Classes ( 2 hours)
- Completeness ( 1 hour)
Laboratory projects (specify number of weeks on each): None.
Estimated Curriculum Category Content:
| Area |
Core |
Advanced |
Area |
Core |
Advanced |
| Algorithms |
|
1 cr |
Data Structures |
|
|
| Software Design |
|
|
Prog. Languages |
|
1 cr |
| Computer Arch |
|
|
Other |
|
1 cr |
Oral and Written Communications:
Social and Ethical Issues:
Theoretical Content:
- Finite automata (DFA, NFA, PDA, TM)
- Grammars
- Arithmetic Hierarchy
- Computational complexity
Problem Analysis: The course analyses the limits of computation, both
absolute and relative to time/space. We analyze specific languages to separate
classes, with respect to models of computation.
Solution Design: : "Solutions" are mathematic proofs, which permeate
the course.
Course Outcomes: The following list documents the course outcomes
and crossreferences them to the BSCS program
outcomes. The letter at the beginning of each reference identifies the program
outcome supported. The numbers sequentially identify the course outcome for
this course. After completing CS 385 a student should have or be able to:
- Use mathematical techniques and principles to define problems in terms
of languages/sets. (a-1)
- Use mathematical techniques and principals to determine which language
family (including regular, context free, and recursive) a particular language
is in. (a-2)
- Use mathematical techniques and principals to reason about the theoretical
difficulty of computational problems. (a-3)
- Detailed knowledge of the fundamentals of the theory of computation.
Including: (a-4)
a. Write and understand recursive definitions of sets.
b. Trace the behavior of simple DFAs, NFAs, PDA, and Turing Machines.
c. Write definitions of regular languages using regular expressions, DFAs,
NFAs, and regular grammars.
d. Apply the Pumping lemma to show that a language is not regular.
e. Know the basic closure properties of regular languages, context free
languages, and recursive languages.
f. Write definitions of context-free languages using context-free grammars
and PDA.
g. Apply the Pumping lemma to show that a language is not context-free.
h. Know the relative computational power of different models of Turing Machines
(multi-tape, semi-infinite tape, etc.)
i. Know the definition of a recursively enumerable language.
j. Know the definition of a recursive language.
k. Know what the Halting problem is.
l. Be able to reduce one undecidable problem to another.
m. Ability to do proof by induction
- Write clear, understandable mathematical proofs. (f-1)
