Formal Languages and Automata Theory
unit 1: (D. Goswami)
Introduction to the course. Texts and References are given.
Unit 2: (D. Goswami)
Alphabet,Strings, Languages, Finite Representation of languages, Regular
Unit 3: (K. V. Krishna)
Context-free 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. Regular grammars.
Unit 4: (D. Goswami)
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, epsilon-transitions.Equivalence of DFAs and
Unit 5: (K. V. Krishna)
Myhill-Nerode Theorem and minimization of finite automata
Unit 6: (D. Goswami)
Establishing the equivalence between regular languages,regular grammars and
Unit 7: (K. V. Krishna)
2DFA, Moore and Mealy automata.
Unit 8: (K. V. Krishna)
Some closure properties of Regular languages -Closure under Boolean operations,
reversal, homomorphism, inverse homomorphism, etc.Pumping lemma, proving
languages to be non regular.
Unit 9: (D. Goswami)
Simplification of CFGs -Removing useless symbols, epsilon- Productions, and unit
productions, Normal forms -CNF and GNF
Unit 10: (K. V. Krishna)
Some closure properties of CFLs -Closure under union, concatenation,Kleene
closure, substitution, homomorphism,reversal, intersection with regular set, etc.
Unit 11: (K. V. Krishna)
Pushdown automata and showing the equivalence between PDA and CFG.
Unit 12: (K. V. Krishna)
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.
Variants of Turing machines.
Unit 13: (K. V. Krishna)
Grammars and grammatically computable functions.
Unit 14: (D. Goswami)
Recursive 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
Unit 15: (K. V. Krishna)
Time bounded TMs, The classes P, NP and NP-complete, Cook’s Theorem,Some
Unit 16: (D. Goswami)
Context-sensitive languages, linear bounded automata and Chomsky Hierarchy.