Applications
of (1) to programming and language specification and
parsing (top-down and bottom-up parsing), and to (2) and (3)
to provability in propositional logic
will be mentioned,
whenever appropriate.

PART I: Languages and Automata

- Basics of language theory: alphabets, strings, concatenation, languages, operations on languages (including Kleene *)
- Deterministic finite automata (DFA's)
- The cross-product construction
- Nondeterministic finite automata (NFA's)
- From NFA's to DFA's, the subset algorithm (Rabin and Scott)
- (*) An Application of NFA's: Text Search
- An introduction to hidden Markov models (HMMs)
- Regular languages and regular expressions
- From regular expressions to NFA's
- From NFA's to regular expressions (node elimination)
- Closure properties of the regular languages
- Right-invariant equivalence relations
- The Nerode/Myhill characterization theorem
- The pumping lemma for regular languages
- State equivalence, minimal DFA's
- Context-free grammars and context-free languages
- Leftmost derivations, rightmost derivations, parse trees
- The universality of leftmost derivations
- Cleaning-up context-free grammars (e-rules, chain rules)
- (*) Chomsky Normal Form
- Right-linear grammars and regular languages
- (*) Eliminating useless productions
- (*) An Introduction to LR-parsing

PART II: Models of Computation; Decidability and Undecidability

- Generalities on computability, Partial Functions
- RAM programs (Post machines)
- Turing Machines
- RAM computable functions are Turing computable
- Turing computable functions are RAM computable
- Recursively enumerable languages and recursive languages
- Pairing Functions
- Coding of RAM programs and Turing machines
- Undecidability of the Halting Problem
- A universal RAM program
- Undecidability and Reducibility
- Rice's Theorem
- (*) The undecidability of Post's Correspondence Problem
- (*) Undecidable Properties of CFL's

PART III: Computational Complexity

- The class P
- Examples of Problems
- Boolean Satisfiability
- The class NP
- NP-completeness
- The Cook-Levin Theorem
- Polynomial-time reductions
- (*) Proof systems for propositional logic:

Gentzen systems; soundness and completeness

Back to Gallier Homepage

*published by:
*