CS 451-3
Theory of Computing
Catalog Description
The fundamental concepts of the theory of computation including finite state acceptors, formal grammars, Turing machines, and recursive functions. The relationship between grammars and machines with emphasis on regular expressions and context-free languages.
Prerequisite:
311 and 330 each with a grade of C or better or graduate standing.
Objectives
To study the fundamental concepts of the theory of computation including finite state machines, formal grammars and languages, Turing machines and recursive functions. To become familiar with the relationships between grammars and machines, and the general properties of formal languages with emphasis on regular expressions and context free languages.
Course Outline
| Lectures | ||
| 1. | Review of mathematical preliminaries | 3 |
| 2. | Abstract machines and languages
Formal grammars. The four types of phase structured grammars. Derivation of sentences. Ambiguity. |
6 |
| 3. | Properties of finite state machines, equivalence, reduction. | 6 |
| 4. | Finite state acceptors, regular grammars, regular expressions, properties of finite state languages. | 6 |
| 5. | Limitations of finite automata, automata with tape. | 2 |
| 6. | Pushdown automata, context free grammars. | 6 |
| 7. | Context free languages, canonical forms, closure properties. | 7 |
| 8. | Turing machines, effective computability, recursive functions. | 4 |
| Total | 40 | |