Computability theory is concerned primarily with determining what tasks can
be accomplished by idealized computer programs. Formal language theory
deals primarily with the ability of certain grammars to express the syntax of
various types of languages. Both fields are branches of formal mathematics.
The former theory has its roots in mathematical logic, the latter in mathematical
linguistics which includes the mathematical theory of compiler design. In
recent years, these two subjects have been studied extensively by computer
scientists and have interacted to the point where, from the perspective of a
computer scientist, they are frequently viewed as a single unified subject. As
such, they have become a standard course topic in many computer science
curricula. This book contains an introduction to these two interrelated subjects.
It is suitable for an introductory course at either the advanced undergraduate
or beginning graduate level. It also can be read and understood,
without the aid of an instructor, by anybody who has either a background in
theoretical mathematics or a reasonable amount of programming experience
and some exposure to mathematical proofs.