Customer Reviews

Introduction to Formal Languages (Dover Books on Mathematics)

5 star:		(0)
4 star:		(2)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

PUBLICATION HISTORY
Dover originally reprinted this book in 1991. I bought it in 1995 and read most of it thru Chapter 8 in Jan-May 2008, finding it to be strongly fascinating. I did stop reading most proofs of theorems somewhere in chapter 3 though. This book has been out of print from Dover for an unknown number of years at this 27Jun11 writing date. Doverpublications.com has recently made a new online store category on computer science and operations research. I've suggested to them that bringing this Revesz book back into print in that category might find a good new audience for it. For example, most existing computer programming languages are based on context-free grammars.

NEW COPY FOUND
By Sep 2011, it looked like Dover will not be reprinting this book. In spite of that low expectation, a dealer called High Plains Thrifters thru Amazon was able to deliver a pristine brand new copy of this out of print book to me on Wed 14Sep11 for $25. A good new copy is exactly what I was after because my read in 2008 / bought in 1995 original copy is hammered into poor condition after 5 months of handling and pencil-marking inside the book during my reading. The long time biggest shortcoming of Dover books is their severely non-durable paper book covers. Theirs are the worst.

THE SUBJECTS IN THIS BOOK
The first two chapters introduce basic concepts and general properties of grammars. It really starts discussing the standard language classes with context-free grammars in Chapter 3, followed by the only treatment I've seen of context-sensitive grammars in Chapter 4. Chapter 5 covers unrestricted phase structure grammars. Then chapter 6 is a good treatment of each of the four Chomsky hierarchy language classes and their relation to the corresponding automata or conceptual machines. There is some very good extended info in this chapter. Chapter 7 concerns itself with the important concepts around decidability, and chapter 8 is a rather difficult treatment of computational complexity theory. Chapter 9 is about Syntax Analysis, and chapter 10 is about Derivation Languages.

THE NATURE OF THIS BOOK AND ITS SUBJECTS
This is a highly technical book, and its contents lie in a zone between mathematical logic, set theory, and linguistics. Included subjects are integral to the theory of computation. The important Chomsky Hierarchy, created by linguist Noam Chomsky in the late 1950s, established four classes of grammars, which are covered in this book. In that system, Type 0 grammars are unrestricted, Type 1 are context-sensitive, Type 2 are context-free, and Type 3 are simplest and are called regular grammars. Type 3 is a subset of Type 2, which is a subset of Type 1, which is a subset of Type 0. This subset relationship of the hierarchy types is because each higher (lower number) type can imitate any lower type by ignoring some of the higher type's capabilities. Type 0 grammars run on Turing machines / Type 1 grammars run on linear-bounded automata / Type 2 grammars run on pushdown automata, and Type 3 grammars run on finite-state automata. This last statement is well-covered in chapter 6 of this book.

OTHER RELATED READING
Before reading most of this book, I had read Parts 1 and 2 in 1st edition of Michael Sipser: 'Introduction to the Theory of Computation' in 2004, so I had already seen some coverage of regular and context-free languages and their automata, plus Turing machine computability issues before in that form. Introduction to the Theory of Computation By Sipser (1st, First Edition)Then in summer 2010, I used this book by Revesz as a reference when reading Alan Parkes' 'Introduction to Languages, Machines, and Logic', which I've already reviewed in Amazon dated 6Jun11. Introduction to Languages, Machines, and Logic

An introduction to theory of formal languages, with a lot of mathematics an no programming.
There are also some chapter on automata, decidability and complexity of computation, but not algorithms on how to parse a program with a computer.
Interesting, concise but I recommend to complete it with a book with some computer program.