CS 553-3
Formal Languages and Automata
Catalog Description
The Chomsky hierarchy of formal grammars and the corresponding classes of automata. Turing machines and basic concepts of computability. Recursive and recursively enumerable languages. Closure properties. Undecidable problems about Turing machines and context-free languages. Deterministic context-free languages and the construction of LR parsers.
Prerequisite:
CS 451.
Objectives
1. To reinforce and extend the student's knowledge of the main results of language and automata theory
2. To appreciate how the theory serves as a unifying framework for other areas of computer science
3. To study one or more particular applications to other areas, such as the construction of parsers for programming languages
Course Outline
| 1. | Basic language and automata theory
Review of finite automata, regular sets, context-free grammars and languages |
6 |
| 2. | Turing Machines
Recursive languages, Turing acceptors, techniques for Turing machine construction, Church's hypothesis, Turing machines as generators, variations and equivalence of Turing machines |
9 |
| 3. | Undecidability
Universal Turing machines, undecidability of the halting problem, recursiveness and recursive enumerability, Post's correspondence problem, and undecidable problems about context-free languages |
9 |
| 4. | The Chomsky hierarchy
Grammars and their relation to automata, relations between classes of languages, LR(0) and LR(1) grammars, parser construction |
8 |
| 5. | Closure properties of families of languages
Abstract families of languages, language operations, closure and decidability properties |
8 |
| Total | 40 | |