Skip to main content

2022 | Book

Automata Theory and Formal Languages

Fundamental Notions, Theorems, and Techniques


About this book

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.

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.

Topics and features:

Provides theorems, examples, and exercises to clarify automata-languages correspondencesPresents some fundamental techniques for parsing both regular and context-free languagesClassifies subclasses of decidable problems, avoiding focus on the theory of complexityExamines finite-automata minimalization and characterization of their behavior using regular expressionsIllustrates how to derive grammars of context-free languages in Chomsky and Greibach normal formsOffers supplementary material on counter machines, stack automata, and abstract language families

This highly useful, varied text/reference is suitable for undergraduate and graduate courses on automata theory and formal languages, and assumes no prior exposure to these topics nor any training in mathematics or logic.

Alberto Pettorossi is professor of theoretical computer science at the University of Rome Tor Vergata, Rome, Italy.

Table of Contents

Chapter 1. Formal Grammars and Languages
In this chapter we introduce some basic notions and some notations we will use in the book. In particular, we introduce the notions of a free monoid, a formal grammar and its generated language, the Chomsky hierarchy, the Kuroda normal form, the Chomsky normal form, and the Greibach normal form. We also examine the effects of the presence of the epsilon production in formal grammars. Finally, we study the derivations in context-free languages and the notions of a substitution and a homomorphism.
Alberto Pettorossi
Chapter 2. Finite Automata and Regular Grammars
In this chapter we introduce the notions of the deterministic finite automata and the nondeterministic finite automata, and we show their equivalence (see Theorem 2.1.14 on page 29). We also prove the equivalence between deterministic finite automata and S-extended type 3 grammars. We introduce the notion of a regular expression (see Section 2.5 on page 41) and we prove the equivalence between regular expressions and deterministic finite automata. We also study the problem of minimizing the number of states of the finite automata and we present a parser for type 3 languages. Finally, we introduce some generalizations of the finite automata and we consider various closure and decidability properties for type 3 languages.
Alberto Pettorossi
Chapter 3. Pushdown Automata and Context-Free Grammars
In this chapter we study the class of pushdown automata and their relation to the class of context-free grammars and languages. We also consider various transformations and simplifications of context-free grammars and we show how to derive the Chomsky normal form and the Greibach normal form of context-free grammars. We then study some fundamental properties of context-free languages and we present a few basic decidability and undecidability results. We also consider the deterministic pushdown automata and the deterministic context-free languages and we present two parsing algorithms for context-free languages.
Alberto Pettorossi
Chapter 4. Linear Bounded Automata and Context-Sensitive Grammars
In this chapter we first show that the notions of the context-sensitive grammars and the type 1 grammars are equivalent. Then we show that every context-sensitive language is a recursive set. Finally, we introduce the class of the linear bounded automata and we show that this class of automata is characterized by the fact that it accepts the set of the context-sensitive languages.
Alberto Pettorossi
Chapter 5. Turing Machines and Type 0 Grammars
In this chapter we establish the equivalence between the class of Turing computable languages and the class of type 0 grammars. In order to present this result, we recall some basic notions about the Turing Machines. More information on Turing Machines can be found in textbooks such as the one by Hopcroft-Ullman [9].
Alberto Pettorossi
Chapter 6. Decidability and Undecidability in Context-Free Languages
This chapter is devoted to the study of the decidability and undecidability properties of (i) the context-free languages, (ii) the deterministic context-free languages, and (iii) the linear context-free languages. We also present the Post Theorem about recursively enumerable sets, the Turing Theorem on the Halting Problem, and the Greibach Theorem about the undecidability of a property for classes of languages.
Alberto Pettorossi
Chapter 7. Supplementary Topics
In this last chapter we consider some more classes of machines and languages, besides those we have studied in the previous chapters. We also present some additional properties of finite automata, regular grammars, context-free grammars, and the so called abstract classes of languages. Finally, we present the Bernstein Theorem and we prove the existence of functions that are not computable.
Alberto Pettorossi
Automata Theory and Formal Languages
Prof. Alberto Pettorossi
Copyright Year
Electronic ISBN
Print ISBN

Premium Partner