Theory of Automata and Formal Languages
Module 1
(2 Lectures) 
Introduction; alphabets, Strings and Languages; automata and Grammars 
Module 2
(3 Lectures) 
Finite automata (FA) its behavior; DFA Formal definition, simplified notations
(state transition diagram, transition table), Language
of a DFA.
NFA Formal definition, Language of an NFA, Removing, epsilontransitions.
Equivalence of DFAs and NFAs 
Module 3
(3 Lectures) 
Regular expressions (RE) Definition, FA and RE, RE to FA, FA to RE, algebraic
laws for RE, applications of REs.
Regular grammars and FA, FA for regular grammar, Regular grammar for FA 
Module 4
(3 Lectures) 
Proving languages to be nonregular Pumping Lenma, applications.
Some closure properties of Regular languages Closure under Boolean operations,
reversal, homomorphism, inverse homomorphism, etc.
M hillNerode theorem 
Module 5
(3 Lectures) 
DFA Minimization
Some decision properties of Regular languages emptiness, finiteness, membership,
equivalence of two DF As or REs, etc. Twoway finite automata,
Finite automata with output 
Module 6
(3 Lectures) 
Contextfree Grammars (CFGs) Formal definition, sentential forms, leftmost and
rightmost derivations,, the language of a CFG. Derivation
tree or Parse tree Definition, Relationship between parse
trees and derivations.
Parsing and ambiguity, Ambiguity in grammars and Languages 
Module 7
(3 Lectures) 
Pushdown Automata (PDA) Formal definition, behavior
and graphical notation, Instantaneous descriptions (Ids), The language of PDA
(acceptance by final state and empty stack). Equivalence
of acceptance by final state and empty stack,
Equivalence of PDAs and CFGs, CFG to PDA, PDA to CFG. 
Module 8
(3 Lectures) 
DPDAs Definition, DPDAs and Regular Languages, DPDAs
and CFLs.
Languages of DPDAs, DPDAs, and ambiguous grammars. 
Module 9
(3 Lectures) 
Simplification of CFGs Removing useless symbols, epsilon
Productions, and unit productions, Normal forms CNF and GNF 
Module 10
(4 Lectures) 
Proving that some languages are not context free Pumping lemma for CFLs, applications.
Some closure properties of CFLs Closure under union, concatenation, Kleene closure,
substitution, homomorphism, reversal, intersection with
regular set, etc. Some more decision properties of CFLs,
Review of some undecidable CFL problems.

Module 11
(6 Lectures) 
Turing Machines TM Formal definition and behavior,
Transition diagrams, Language of a TM, TM as accepters and deciders.
TM as a computer of integer functions
Programming techniques for TMs Storage in state, multiple tracks, subroutines,
etc.
Variants of TMs Multitape TMs, Nondeterministic TMs.
TMs with semiinfinite tapes, multistack machines.
Equivalence of the various variants with the basic model 
Module 12
(2 Lectures) 
Recursive and recursively enumerable languages, Some properties of recursive
and recursively enumerable languages, Codes for TMs. A
language that is not recursively enumerable (the diagonalization
language). The universal language, Undecidability of the
universal language, The Halting problem, Undecidable problems
about TMs. 
Module 13
(2 Lectures) 
Post's Correspondence Problem (PCP) Definition, Undecidability of PCP.
Other undecidability problems e.g. some problems related to CFLs 
Module 14
(2 Lectures) 
Context sensitive language and linear bounded automata. Chomsky hierarchy 
Download
Syllabus (PDF)
