Fall 98, 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.