Description
OXFORD Formal Languages And Automata Theory 2011 Edition by Nagpal
Formal Languages and Automata Theory is designed to serve as a textbook for undergraduate and postgraduate students of engineering (computer science and information technology) and computer applications.The book provides extensive coverage of essential topics such as computability, formal languages, models of computation-automation, complexity theory, NP completeness, and decidability.Beginning with the basic aspects of automata theory and its relevance to computer science, the book goes on to discuss the concepts of formalism and computability and discrete mathematical structures. A discussion of important topics such as regular sets and grammar, context-free languages, and various types of automata such as deterministic finite automata, nondeterministic finite automata, pushdown automata, linear-bound automata is provided. Special emphasis is laid on the design and applications of Turing machines. The book also provides an in-depth discussion on the topic of decidability and its association with recursive and recursively enumerable languages. Explicit coverage has been given to time complexity aspect of computability and its manifestation in the form of P and NP classes. Table of contentsChapter 1. Automata, Formal Languages, and ComputabilityChapter 2. Mathematical PreliminariesChapter 3. Finite AutomataChapter 4. Regular Grammar and Regular SetsChapter 5. Context-free Grammars and LanguagesChapter 6. Pushdown AutomataChapter 7. Turing MachinesChapter 8. The Pitfall of Algorithmic Computing: UndesirabilityChapter 9. Computable FunctionsChapter 10. Computational Complexity: Tractable and Possibly Intractable ProblemsOnline Resources