Formal Languages and Automata Theory

by K V N Sunitha, N. Kalyani

Intended for the students of computer science, information technology and mathematics, this book offers a concise and coherent explanation of the important concepts of Automata Theory. It emphasizes on formal languages, models of computation, computability, complexity theory and also provides the conceptual tools that practitioners use in computer engineering. Table Of Contents: 1. Mathematical Preliminaries and Formal Languages 2. Finite Automata 3. Regular Languages and Regular Grammars 4. Context Free Grammars and Context Free Languages 5. Pushdown Automata 6. Turing Machines 7. Undecidability and Computability 8. NP-Completeness 9. LR(K) and LL(I) Grammar; Appendix: Proposition and Predicate Logic A. l Propositions A.2 Connectives A.3 Well-formed Formula (WFF) A.4 Logical Identities A.5 Normal Forms of Well-formed Formulas A.6 Principal Disjunctive Normal Form A.7 Predicate Calculus A.8 Universal and Existential Quantifier A.9 Well-formed Formulas of Predicate Calculus A.I0 Rules of Inferel1ce for Predicate Calculus Special Features: Extensive coverage of important topics such as Finite Automata, Pushdown Automata, Undecidibility, etc. Lays emphasis on the importance of Turing machines as language recognizers, language generators and as computing models Uses stepwise approach Excellent pedagogy 268 Solved examples 318 Multiple-choice questions 142 Exercise questions 220 Illustrations

Paperback

Published June 8, 2010