An Introduction to Formal Language Theory
Robert N. Moll, Michael A. Arbib, A. J. Kfoury, James Pustejovsky[From the Back Cover]
An Introduction to Formal Language Theory is the first text to integrate an exposition of the theory underlying syntax and parsing of programming languages with a thorough discussion of issues in computational linguistics and the grammar of natural languages. The book begins with standard formal language material, including a discussion of regular, context-free, context sensitive, and arbitrary phrase structure languages. This material is followed by a discussion of the corresponding families of automata: finite-state, push-down, linear bounded, and Turing machines. Important topics introduced along the way include closure properties, normal forms, nondeterminism, basic parsing algorithms, and the theory of computability and undecidabiiity.
The role of algebraic techniques in formal language theory is emphasized through a chapter devoted to the fixed point approach to the analysis of context-free languages. Advanced topics in parsing are also emphasized in an unusually clear and precise presentation.
A unique feature of the book is the two-chapter introduction to the formal theory of natural languages. Chomsky's theory is presented in a historical perspective ranging from the classic approach using transformations to the core concepts of government and binding. Alternative schemes for representing natural language are also discussed, in particular Augmented Transition Networks and Generalized Phrase Structure Grammar.
This book is part of the AKM Series in Theoretical Computer Science. A Basis for Theoretical Computer Science, also in the series, provides the necessary background for this volume, which is Intended to serve as a text for upper-division undergraduateand graduate-Ievei students in both computer science and linguistics.