Fall 98, CSE 468:
Detailed description of the contents of the course


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.