CMSC 452 ELEMENTARY THEORY OF COMPUTATION

Catalog Description

Introduction to alternative theoretical models of computation, types of automata, and their relations to formal grammars and languages.

Introduction of formal models of computing, types of automata, and their relations to formal grammars and languages.

CMSC 214 and CMSC 251.

Mathematical Preliminaries (1 week)
Induction, relations, cardinality, diagonalization.
Regular languages and Finite Automata (3 weeks)
Deterministic finite acceptors (DFA) and regular expressions, equivalence of languages accepted by a DFA and regular languages, closure properties of regular languages, nondeterministic finite acceptors (NDFA) and their equivalence with DFA, nonregular languages and the pumping lemma.
Context free grammars and context free languages (CFL) (3 weeks)
Pushdown acceptors (PDA), equivalence of CFL and languages accepted by PDA, closure properties of CFL, non-CFL and the pumping lemma for CFL, recognition of CFL and parsing.
Primitive recursive functions, Turing Machines, other models of computation (4 weeks)
Universal Turing machines, Church's Thesis, the halting problem for Turing machines, unsolvable problems, recursive and recursively enumerable sets.

J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
Lewis and Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.