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.