##
*Fall 2000, CSE 468: *

Detailed description of the contents of the course

#### Preliminaries

Overview of basic notions used in the course:
Mathematical objects (sets, relations, functions).
Languages (alphabet, strings).
Principle of induction (mathematical, structural, well-founded).
Recursive definitions.
#### Regular Languages and Finite Automata

Regular languages and expressions,
Finite Automata. Acceptability.
Nondeterministic FA.
Correspondence between RLs and FA.
(Kleene's Theorem).
The Myhill-Nerode theorem and
minimization of FA.
The pumping lemma for RLs.
Decision problems.
#### Context-Free Languages and Pushdown Automata

Context-free grammars. Derivation trees. Ambiguity.
Normal forms. Deterministic PA.
Parsing. The pumping lemma for CFLs.
Closure properties of CFLs;
Decision problems.
#### Turing Machines

Models of computation and the Church-Turing Thesis.
The TM model.
Nondeterministic TMs.
The Universal TM.
Recursively enumerable and recursive languages.
Unrestricted grammars and TMs.
The Chomsky Hierarchy.
#### Undecidability and Computability

Unsolvable problems.
Rice's theorem. Post's correspondence problem.
Primitive recursion. Minimalization operator.
mu-Recursive functions and computability.