Automata Theory and Formal Theory Languages

In this book we present some basic notions and results on Automata Theory, Formal 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. Chapter 6 of the book is dedicated to the analysis of various decidability and undecidability problems in context-free languages. In the Supplementary Topics chapter we deal with other classes of machines and languages, such as the counter machines, the stack automata, and the abstract families of languages. We also present some additional properties of finite automata, regular grammars, and context-free grammars, and we present a sufficient condition for the existence of a bijection between sets and we prove the existence of functions that are not computable.