Formal Language & Automata Theory

Module 1
Introduction: Alphabet, languages and grammars, productions and derivation,
Chomsky hierarchy of languages.
Regular languages and finite automata: Regular expressions and languages,
deterministic finite automata (DFA) and equivalence with regular expressions,
nondeterministic finite automata (NFA) and equivalence with DFA, regular grammars
and equivalence with finite automata, properties of regular languages, pumping lemma
for regular languages, minimization of finite automata.
Module 2
Context-free languages and pushdown automata: Context-free grammars (CFG) and
Context-free languages (CFL), Chomsky and Greibach normal forms, nondeterministic
pushdown automata (PDA) and equivalence with CFG, parse trees, ambiguity in CFG,
pumping lemma for context-free languages, deterministic pushdown automata, closure
properties of CFLs.
Module 3

Context-sensitive languages: Context-sensitive grammars (CSG) and Context-
sensitive languages, linear bounded automata and equivalence with CSG.

Module 4
Turing machines: The basic model for Turing machines (TM), Turing recognizable

(Recursively enumerable) and Turing-decidable (recursive) languages and their closure
properties, variants of Turing machines, nondeterministic TMs and equivalence with
deterministic TMs, unrestricted grammars and equivalence with Turing machines, TMs
as enumerators.
Module 5
Undecidability: Church-Turing thesis, universal Turing machine, the universal and
diagonalization languages, reduction between languages and Rice’s theorem,
undecidable problems about languages.