# CS 385

From CS Wiki

### Theory of Computation

**Catalog Description:** Mathematical models of computation, including finite automata and Turing machines. Same as Math 385.

**Type:** Required for all CS majors.

**Total Credits:** 3

**Contact Hours:** 3 lecture hours per week

**Course Coordinator**: Terry Soule

**URL:** http://www2.cs.uidaho.edu/~cs385/f12/ (Fall 2012)

http://www.webpages.uidaho.edu/~markn/385/ (Fall 2013)

**Prereq:** Have passed all required CS 2XX level course with C or better.

**Textbook:** P. Linz, *An Introduction to Formal Languages and Automata*, 5th Edition, Peter Linz, 2006 or similar text.

**Textbook URL:** http://www.jblearning.com/catalog/9781449615529/

**Prerequisites by Topic**:

- Trees, graphs, worst case analysis, recursion (CS 121)
- Induction, counting (Math 175)
- Series, set theory (Math 176)

## Major Topics Covered

- Language Theory: Recursive definitions ( 2 hours)
- Language Theory: Regular expressions and languages ( 2 hours)
- Language Theory: Finite automata ( 2 hours)
- Language Theory: Kleene's theorem ( 1 hour)
- Language Theory: Nondeterminism ( 4 hours)
- Language Theory: Pumping lemma (2 hours)
- Language Theory: Finite automata with output ( 2 hours)
- Language Theory: Nonregular languages ( 4 hours)
- Language Theory: Pushdown automata ( 2 hours)
- Language Theory: Contex-free grammars ( 2 hours)
- Language Theory: Chomsky normal form ( 2 hours)
- Language Theory: Non-context-free grammars and languages ( 3 hours)
- Computability Theory: Turing machines ( 3 hours)
- Computability Theory: The Halting problem ( 1 hour)
- Computability Theory: Rice's theorem ( 1 hour)
- Computability Theory: Complexity Classes ( 2 hours)
- Computability Theory: Completeness ( 1 hour)

## Course Outcomes

- Use mathematical techniques and principles to define problems in terms of languages/sets. (a)
- Use mathematical techniques and principals to determine which language family (including regular, context free, and recursive) a particular language is in. (a)
- Use mathematical techniques and principals to reason about the theoretical difficulty of computational problems. (a)
- Write and understand recursive definitions of sets. (a)
- Trace the behavior of simple DFAs, NFAs, PDA, and Turing Machines. (a)
- Write definitions of regular languages using regular expressions, DFAs, NFAs, and regular grammars. (a)
- Apply the Pumping lemma to show that a language is not regular. (a)
- Know the basic closure properties of regular languages, context free languages, and recursive languages. (a)
- Write definitions of context-free languages using context-free grammars and PDA. (a)
- Apply the Pumping lemma to show that a language is not context-free. (a)
- Know the relative computational power of different models of Turing Machines (multi-tape, semi-infinite tape, etc.) (a)
- Know the definition of a recursively enumerable language. (a)
- Know the definition of a recursive language. (a)
- Know what the Halting problem is. (a)
- Be able to reduce one undecidable problem to another. (a)
- Ability to do proof by induction (a)
- Write clear, understandable mathematical proofs. (f)