
Overview:
Followings are the syllabus and reference books for Formal Language and Automata Theory
Syllabus:
Finite State Machines : Definition, concept of sequential circuits, state table & state assignments, concept of
synchronous, asynchronous and liner sequential machines.
Finite State Models : Basic definition, mathematical representation, Moore versus Mealy m/c, capability & limitations
of FSM, state equivalence & minimization, machine equivalence, incompletely specified machines, merger graph &
compatibility graph, merger table, Finite memory, definite, information loss less & inverse machines : testing table &
testing graph.
Structure of Sequential Machines : Concept of partitions, closed partitions, lattice of closed partitions, decomposition :
serial & parallel.
Finite Automation : Preliminaries (strings, alphabets & languages, graphs & trees, set & relations), definition,
recognition of a language by an automata  idea of grammar, DFA, NFA, equivalence of DFA and NFA, NFA with emoves,
regular sets & regular expressions : equivalence with finite automata, NFA from regular expressions, regular
expressions from DFA, two way finite automata equivalence with one way, equivalence of Moore & Mealy machines,
applications of finite automata.
Closure Properties of Regular Sets : Pumping lemma & its application, closure properties minimization of finite
automata : minimization by distinguishable pair, MyhillNerode theorem.
Context Free Grammars : Introduction, definition, derivation trees, simplification, CNF & GNF.
Pushdown Automata : Definition, moves, Instantaneous Descriptions, language recognised by PDA, deterministic
PDA, acceptance by final state & empty stack, equivalence of PDA and CFL.
Closure Properties of CFLs : Pumping lemma & its applications, ogden’s lemma, closure properties, decision
algorithms.
Introduction to Z. Regular language properties and their grammars. Context sensitive languages.
Books and Links:
Text books :
1. Hopcroft JE. and Ullman JD., “Introduction to Automata Theory, Languages &
Computation”, Narosa.
2. K.L.P Mishra &N. Chandrasekharan – “Theory of Computer Science”, PHI
3. Ash &Ash – “Discrete Mathematics”,TMH
4. Martin—Introduction
5. Lewis H. R. and Papadimitrou C. H., “Elements of the theory of Computation”, P.H.I.
6. Kain, “Theory of Automata &Formal Language”, McGraw Hill.
References :
1. Kohavi ZVI, “Switching &Finite Automata”, 2nd Edn., Tata McGraw Hill.
2. Linz Peter, “An Introduction to Formal Languages and Automata”, Narosa
3. “Introduction to Formal Languages”, Tata McGraw Hill, 1983.
Back
