Formal Languages and Automata: Mathematics : Theory of Computation

The study of formal languages constitutes an important subarea of computer science and theoretical mathematics. This area sprang to life around 1956 when Noam Chomsky gave a mathematical model of a grammar in connection with his study of natural languages. Shortly afterwards, the concept of a grammar was found to be of great importance to the programmer when the syntax of the programming language ALGOL was defined by a context-free grammar. This development led naturally to syntax-directed compiling and the concept of a compiler. Since then a considerable flurry of activity has taken place, the results of which have related formal languages and automata theory to such an extent that it is impossible to treat the areas separately. By now, no serious study of computer science would be complete without a knowledge of the techniques and results from language and automata theory.This book presents the theory of formal languages as a coherent theory and makes explicit its relationship to automata which begins with an explanation of the notion of a finite description of a language. The fundamental descriptive device--the grammar--is explained, as well as its three major subclasses--regular, context-free, and context-sensitive grammars.The context-free grammars are treated in detail, and such topics as normal forms, derivation trees, and ambiguity are covered. Four types of automata equivalent to the four types of grammars are described. These automata arethe finite automaton, the pushdown automaton, the linear bounded automaton, and the Turing machine. The Turing machine is covered in detail, and insolvability of the halting problem shown. The book concludes withcertain advanced topics in language theory--closure properties, computational complexity, deterministic pushdown automata, LR(k) grammars, stack automata, and decidability.The emphasis is on ideas and ease of understanding rather than undue formalism. In some cases, the details of long and tedious proofs are omitted. However, in all cases sufficient intuitive explanation is given so that the reader may easily provide the rigorous proof if desired.The intention herein is primarily as a textbook for a first- or second-year graduate course in formal languages. It is self-contained and presupposes only the normal level of maturity expected of a beginning graduate student.Although not essential, it has been found that a course in finite state or Turing machines is useful preparation. The book is not intended as a research monogram on formal languages, although it covers many of the known results, and much of the material presented previously existed only in journals of mathematics and computer science. The chapters are provided with a guide to references on the material covered and related topics. The last chapter presents the concepts and issues with Decidable/Undecidable questions and problem equivalence.The material is based upon class notes from courses at Princeton and the University of Pennsylvania in addition to the author’s research. The Computer Science theory was studied under Dr. Samuel D. Bedrosian with the theoretical mathematics from the work of Dr. Herbert S. Wilf both former professors at the University of Pennsylvania in addition to professors Douglas Clark, Perry Cook and Richard Lipton former Princeton University professors.DCP