Automata Theory and Formal Languages

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.<div><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></div>