Pin It


TCS-403 Theory Of Automata & Formal Language

>>Send ur suggestion to Mynotes Tab

Unit  I        
Introduction to defining language, Kleene closures, Arithmetic expressions, defining grammar, Chomsky hierarchy, Finite Automata (FA), Transition graph, generalized transition graph.
Unit  II      
Nondeterministic finite Automata (NFA), Deterministic finite Automata (DFA), Construction of DFA from NFA and optimization, FA with  output: Moore machine, Mealy machine and Equivalence, Applications and Limitation of FA.
Unit  III    
Arden Theorem, Pumping Lemma for regular expressions, Myhill-Nerode theorem, Context free grammar:Ambiguity, Simplification of CFGs, Normal forms for CFGs, Pumping lemma for CFLs, Decidability of CFGs, Ambiguous to Unambiguous CFG.
Unit IV      
Push Down Automata (PDA): Description and definition, Working of PDA, Acceptance of a string by PDA, PDA and CFG, Introduction to auxiliary PDA and Two stack PDA.
Unit  V     
Turing machines (TM): Basic model, definition and representation, Language acceptance by TM, TM and Type – 0 grammar, Halting problem of TM, Modifications in TM, Universal TM, Properties of recursive and recursively enumerable languages, unsolvable decision problem, undecidability of Post correspondence problem, Church’s Thesis, Recursive function theory.

Text Books: 
1. Hopcroft, Ullman, “Introduction to Automata Theory, Language and Computation”, Nerosa Publishing House, 3rd Edition : Direct Link to the Book
2. K.L.P. Mishra and N.Chandrasekaran, “Theory of Computer Science(Automata, Languages and Computation)”, PHI, 3rd Edition : Direct Link to the Book

Reference Books: 
1.  Martin J. C., “Introduction to Languages and Theory of Computations”, TMH
2.  Papadimitrou, C. and Lewis, C.L., “Elements of theory of Computations”, PHI
3.  Cohen D. I. A., “Introduction to Computer theory”, John Wiley & Sons
4.  Kumar Rajendra, “Theory of Automata (Languages and Computation)”, PPM


INFORMATION AND LINKS REGARDING B.TECH C.S. Coming Soon With All Other Branch's Notes......

Powered by Blogger.

©2011- 2013 Csdoon : Easy Notes All Rights Reserved