Theory Of Automata And Formal Languages
Technical Publications, 2007 - 361 pages
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
algorithm alphabet called compute concatenation consider Construct context free grammar context free language Convert the given defined denoted derivation tree Design deterministic finite automata equal number equivalent DFA Example final finite set given CFG given NFA grammar G HALT Hence induction input set input string input symbol input tape integer length Let us solve Mealy machine means Moore machine Move left Move right nodes null string number of a's obtain odd number output pair palindrome problem production rules Proof prove pumping lemma push down automata q0 and qj recursively enumerable languages regular expression regular language remainder represented set of strings Similarly Solution stack statement substring terminal symbols theorem transition diagram transition function transition graph transition table turing machine unit production useless symbol zeros