Courses
CS 473: Automata, Grammars and Languages
| Objective |
- To introduce the fundamental models of computation used throughout computer
science: finite automata, pushdown automata, and Turing machines. To understand
the limitations of computation and the complexity of computation (i.e., what
can and what cannot be computed, and what can be computed using a realistic
amount of resources?).
|
| Pre-Conditions |
|
Post-Conditions
(Topics) |
- Finite automata and regular expressions
- Properties of regular sets
- Context-free grammars and pushdown automata
- Properties of context-free languages
- Recursive and recursively-enumerable sets
- Turing machines
- Church's thesis
- Universal machines
- Undecidability and reducibility
- Complexity classes P, NP, and NP-completeness
|
Last revised on 25 February 1997 by
Todd Proebsting.
