The book consists of five chapters. Chapter 1, Mathematical Background, consists of the material on set theory, induction principles for the natural numbers, and trees and inductive definitions that is required in the remaining chapters. In Chapter 2, Formal Languages, we say what symbols, strings, alphabets and (formal) languages are, introduce and show how to use several string induction principles, and give an introduction to the Forlan toolset. The remaining three chapters introduce and study more restricted sets of languages.
In Chapter 3, Regular Languages, we study
regular expressions and languages,
four kinds of finite automata, algorithms for processing and converting
between regular expressions and finite automata, properties of regular languages,
and
applications of regular expressions and finite automata to
searching in text
files and lexical analysis.
In Chapter 4, Context-free Languages, we study context-free grammars and
languages, algorithms for processing grammars and for converting regular expressions
and finite automata to grammars, and properties of context-free languages.
It turns out that the set of all context-free languages is a proper superset
of the set of all regular languages.
Finally, in Chapter 5, Recursive and Recursively Enumerable Languages, we
study a universal
programming language based on Lisp, which we use to define
the recursive and recursively enumerable languages. We study algorithms for
processing programs and for converting grammars to programs, and properties
of recursive and recursively enumerable languages. It turns out that the contextfree
languages are a proper subset of the recursive languages, that the recursive
languages are a proper subset of the recursively enumerable languages, and that
there are languages that are not recursively enumerable. Furthermore, there
are problems, like the halting problem (the problem of determining whether a
program P halts when run on an input w), or the problem of determining if two
grammars generate the same language, that can’t be solved by programs.
