Fall 2000, 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).
Regular Languages and Finite Automata
Regular languages and expressions,
Finite Automata. Acceptability.
Correspondence between RLs and FA.
The Myhill-Nerode theorem and
minimization of FA.
The pumping lemma for RLs.
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;
Models of computation and the Church-Turing Thesis.
The TM model.
The Universal TM.
Recursively enumerable and recursive languages.
Unrestricted grammars and TMs.
The Chomsky Hierarchy.
Undecidability and Computability
Rice's theorem. Post's correspondence problem.
Primitive recursion. Minimalization operator.
mu-Recursive functions and computability.