Automata and Formal Languages(C)

AUTOMATA AND FORMAL LANGUAGES (C)
Part IA Numbers and Sets is essential.

Register machines

Deﬁnition of a register machine; recursive functions, recursively enumerable sets. Church’s thesis. Undecidability of the halting problem for register machines. Universal register machines. The recursion theorem. The s-m-n theorem. Other undecidable problems: reduction and Rice’s theorem. [9]

Regular languages and ﬁnite-state automata

Deterministic ﬁnite-state automata (DFA) and regular languages. Nondeterminism. Regular expressions. Limitations of ﬁnite-state automata: homomorphisms and closure properties; the pumping lemma; examples of non-regular languages. Minimization and the use of equivalence relations and quotients to construct minimal DFAs. [9]

Pushdown automata and context-free languages

Context-free grammars and context-free languages: generating languages by replacement rules. Normal forms for context-free languages, the Chomsky normal form; regular languages are context-free. Limitations of context-free grammars: the pumping lemma for context-free languages; examples of noncontext-free languages. Pushdown automata. [6]

Appropriate books

- J.E. Hopcroft, R. Motwani and J.D. Ullman Introduction to automata theory, languages and computation, 3rd edn. Pearson 2006
- P.T. Johnstone Notes on logic and set theory (Chapter 4). CUP 1987
- † D.C. Kozen Automata and computability. Springer 1997
- R.I. Soare Recursively enumerable sets and degrees: a study of computable functions and computably generated sets. Springer (Perspectives in mathematical logic) 1987
- M. Sipser Introduction to the theory of computation. Wadsworth Publishing Co 2012

Associated GitHub Page