Formal languages and automata theory - Nagpal, C.K. (Oxford, United Kingdom : Oxford University Press, 2011)
Formal Languages and Automata theory presents the theoretical aspects of computer science, and helps define infinite languages in finite ways; construct algorithms for related problems and decide whether a string is in language or not. These are of practical importance in construction of compilers and designing of programming languages, thus establishing the course as a core paper in third/fourth year of various universities. This book adopts a holistic approach to learning from fundamentals of formal languages to undecidability problems. Its organization follows the order in which the course is taught over the years, and is well-accepted by the student community. The contents of each topic motivate the reader to easily understand the concepts rather than remember and reproduce.
1. Automata, formal languages and computability -- 2. Mathematical preliminaries -- 3. Finite automata -- 4. Regular grammar and regular sets -- 5. Context-free grammars and languages -- 6. Pushdown automata -- 7. Turing machines -- 8. The pitfall of algorithmic computing: undecidability -- 9. Computable functions -- 10. Computational complexity: tractable and possibly intractable problems.
Includes index.
Keywords: FORMAL LANGUAGES