Theory Of Automata And Formal Languages

Front Cover
Technical Publications, Jan 1, 2007 - 361 pages
4 Reviews
Defining language,Kleen closures, Arithmetic expressions, Defining grammar, Chomsky hierarchy, Finite Automata (FA), Transition graph, Generalized transition graph.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.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.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.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, Godel numbering.

What people are saying - Write a review

User Review - Flag as inappropriate

My teacher is giving homework having all question is from A.A.Puntambekar's book. Also I had fun while solving automata problems.

User Review - Flag as inappropriate

I feel comphertable with this book, thank you so much

Common terms and phrases

Bibliographic information