Descrizione

In this book we present the basic notions of formal language theory and automata 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 behavior 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 Appendix we deal with other classes of machines and languages, such as the counter machines, the stack automata, and the abstract families of languages.

Dettagli