Automata Theory and Formal Languages

In this book we present some basic notions and results on Automata Theory, For- mal Language Theory, Computability Theory, and Parsing Theory. In particular, we consider the class of regular languages which are related to the class of finite automata, and the class of the context-free languages which are related to the class of pushdown automata. For the finite automata we also study the problem of their minimalization and the characterization of their behaviour using regular expressions. For context-free languages we illustrate how to derive their grammars in Chomsky and Greibach normal form. We study the relationship between deterministic and nondeterministic pushdown automata and the context-free languages they accept. We present also some fundamental techniques for parsing both regular and context- free languages. Then we consider more powerful automata and we illustrate the relationship between linear bounded automata and context-sensitive languages, and between Turing Machines and type 0 languages. A chapter of the book is dedicated to the analysis of various decidability and undecidability problems in context-free languages. In the Appendices we deal with other classes of machines and languages, such as the counter machines, the stack automata, and the abstract families of languages.