CS 512-Formal Language & Automata Theory |
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 lossless & 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, myhill-nerode 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 ZRL & CSL |
Introduction to Z. Regular language properties and their grammars, Context sensitive languages. |
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. Lewis H. R. and Papadimitrou C. H., “Elements of the theory of Computation”, P.H.I.
5. Martin: Introduction to Languages and Theory of Computation”, 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.
|
|