Automata Theory and Formal Languages Fundamental Notions, Theorems, and Techniques

Knowledge of automata theory and formal languages is crucial for understanding human-computer interaction, as well as for understanding the various processes that take place when manipulating knowledge if that knowledge is, indeed, expressed as sentences written in a suitably formalized language. In particular, it is at the basis of the theory of parsing, which plays an important role in language translation, compiler construction, and knowledge manipulation in general.<p></p><p>Presenting basic notions and fundamental results, this concise textbook is structured on the basis of a correspondence that exists between classes of automata and classes of languages. That correspondence is established by the fact that the recognition and the manipulation of sentences in a given class of languages can be done by an automaton in the corresponding class of automata. Four central chapters center on: finite automata and regular languages; pushdown automata and context-free languages; linear bounded automata and context-sensitive languages; and Turing machines and type 0 languages. The book also examines decidable and undecidable problems with emphasis on the case for context-free languages.</p><p><b>Topics and features:</b></p><ul><li>Provides theorems, examples, and exercises to clarify automata-languages correspondences</li><li>Presents some fundamental techniques for parsing both regular and context-free languages</li><li>Classifies subclasses of decidable problems, avoiding focus on the theory of complexity</li><li>Examines finite-automata minimalization and characterization of their behavior using regular expressions</li><li>Illustrates how to derive grammars of context-free languages in Chomsky and Greibach normal forms</li><li>Offers supplementary material on counter machines, stack automata, and abstract language families</li></ul><p></p><p></p><p></p><p></p><p></p><p></p><p>This highly useful, varied text/reference is suitable for undergraduate and graduatecourses on automata theory and formal languages, and assumes no prior exposure to these topics nor any training in mathematics or logic.</p><p><b>Alberto Pettorossi<i> </i></b>is professor of theoretical computer science at the University of Rome Tor Vergata, Rome, Italy.</p>