Formal grammars in linguistics and psycholinguistics, vol. 1: An introduction to the theory of formal languages and automata. By Willem J. M. Levelt. Amsterdam: John Benjamins, 2008. Pp. xi, 139. ISBN 9789027232502. $43.95.
Aravind K. Joshi · Language · 2011
Reviewed by: Formal grammars in linguistics and psycholinguistics, vol. 1: An introduction to the theory of formal languages and automata Aravind K. Joshi Formal grammars in linguistics and psycholinguistics, vol. 1: An introduction to the theory of formal languages and automata. By Willem J. M. Levelt. Amsterdam: John Benjamins, 2008. Pp. xi, 139. ISBN 9789027232502. $43.95. This monograph is a reedition of a book that was originally published in 1974 as the first of a three-volume set entitled Formal grammars in linguistics and psycholinguistics. The original three volumes have been reissued by John Benjamins as a single bound book with a new postscript. This review focuses on Vol. 1 of the monograph version, An introduction to the theory of formal languages and automata, although brief reference will be made to the other volumes and the postscript. After introducing the general definitions of grammar and automata in Ch. 1, 'Grammars as formal systems', the well-known hierarchy of grammars, the so-called Chomsky hierarchy, is presented with clear definitions and examples in Ch. 2, 'The hierarchy of grammars'. In just these twenty-five or so pages, L presents not only definitions and examples for regular grammars (finite-state grammars), context-free grammars, and context-sensitive grammars but also the normal [End Page 414] forms for each of these three classes of grammars. Usually one sees the Chomsky normal form for context-free grammars; however, the Greibach normal form is also presented here with an example, which is very useful in motivating the connection to pushdown automata. While discussing context-sensitive grammars, the author introduces some of the normal forms for these grammars, including the Kuroda normal form. Usually we do not see this normal form discussed in books on the theory of computation. However, it is appropriate that it appears here since Kuroda (1964) characterized it as a 'linear bounded grammar'analogous to the so-called linear-bounded automata, discussed by the author in Ch. 6. The normal form A → β / φ1 − φ2 is also introduced. It would have been better if it had been pointed out here or later in the book that this normal form was the basis of a suggestion by McCawley (1968) that context-sensitive grammars are very often used in linguistics as constraints on structural descriptions and not as rules for generation. Given that statistical grammars and parsing took off only around the mid-1990s, it is nice to see in Ch. 3 ('Probabilistic grammars') that this topic was discussed at this early date. This chapter deals with issues such as the consistency of probabilistic models and normal forms, the latter creating some problems for building a probabilistic model based on the normal forms. The discussion is quite detailed and is supplemented with helpful examples. This chapter should receive significant attention, given that immense activity in statistical parsing is currently taking place. Chs. 4, 5, and 6 deal with the automata corresponding to the three types of formal grammars discussed in Ch. 2. The discussion of finite-state automata (deterministic and nondeterministic) is quite detailed and is well connected to the material on finite-state grammars (Ch. 4). The same is true for the discussion of pushdown automata (Ch. 5). The chapter on linear-bounded automata (Ch. 6) corresponding to the context-sensitive grammars is a nice addition. Usually one does not find these topics discussed in the linguistic context, so it is useful to have this material available to the readers in order that they may appreciate the different modes of introducing contextual information in the formulation of formal grammars relevant to linguistic descriptions. This is discussed in the postscript, to which I return later. Ch. 7 deals with 'Turing machines', the grammatical equivalence of the so-called unrestricted rewriting systems (Post production systems). Although these systems are not directly relevant to the formulation of linguistic theories, they are important for bringing out the notions of recursive enumerability and recursiveness. The last chapter (Ch. 8) concerns grammatical inference. To see a discussion of grammatical inference and the associated probability models as early as 1974 is a pleasant surprise! At present, as noted above, statistical parsing is a major topic in computational linguistics. Although Vol...