Levelt W.J.M. An Introduction to the Theory of Formal Languages and Automata

Издательство John Benjamins, 2008, -152 pp.In the latter half of the 1950’s, Noam Chomsky began to develop mathematical models for the description of natural languages. Two disciplines originated in his work and have grown to maturity. The first of these is the theory of formal grammars, a branch of mathematics which has proven to be of great interest to information and computer sciences. The second is generative, or more specifically, transformational linguistics. Although these disciplines are independent and develop each according to its own aims and criteria, they remain closely interwoven. Without access to the theory of formal languages, for example, the contemporary study of the foundations of linguistics would be unthinkable.
The collaboration of Chomsky and the psycholinguist George Miller, around 1960, led to a considerable impact of transformational linguistics on the psychology of language. During a period of near feverish experimental activity, psycholinguists studied the various ways in which the new linguistic notions might be used in the development of models for language user and language acquisition. A good number of the original conceptions were naïve and could not withstand critical test, but in spite of this, generative linguistics has greatly influenced modern psycholinguistics.
The theory of formal languages, transformational linguistics, psycholinguistics, and their mutual relationships have been the theme of my three-volume book Formal Grammars in Linguistics and Psycholinguistics, published in 1974. Volume I of Formal Grammars was an introduction to the theory of formal languages and automata; grammars are treated only as formal systems in that volume. Volume II in turn dealt with applications of those mathematical models to linguistic theory. Volume III, finally, treated applications of grammatical systems to models of the language user and language learner, i.e., psycholinguistic applications. A new, single-volume edition of Formal Grammars is about to appear with John Benjamins Publishing Company.
The present text is a re-edition of Volume I. It is an entirely self-contained introduction to the theory of formal grammars and automata, which hasn’t lost any of its relevance. Of course, major new developments have seen the light since this introduction was first published, but it still provides the indispensible basic notions from which later work proceeded. Moreover, I had undertaken the writing of this text for three reasons, which are still relevant. First, other available texts tend to be beyond the reach of many students of linguistics and psychology because they suppose an acquaintance with sophisticated mathematical theories and methods. The present introduction is kept at a rather elementary level; a general knowledge of college mathematics will be sufficient to follow the text, although familiarity with the elements of set theory and statistics will certainly be an advantage.
Second, I intended to write an introduction specifically for linguists and psycholinguists. Other introductions often treat a number of subjects which have little obvious relation to linguistics or psychology, or alternatively lack a treatment of topics which are especially relevant to students of language. Probabilistic grammars and grammatical inference, for example, were not treated at the time in any of the existing introductions, whereas, over the years, their relevance for linguistics and psycholinguistics have become obvious.
The third reason for writing this introduction was, of course, to provide students of language with a reference text for the basic notions in the theory of formal grammars and automata, as they keep being referred to in linguistic and psycholinguistic publications, among them my Formal Grammars. The subject index of this introduction can be used to find definitions of a wide range of technical terms: definitions are indicated by italicized page numbers.
I am much aware of important theoretical progress in this field over the last three decades, much of which has found applications in linguistic and psycholinguistic theory. I therefore add an appendix with further references to some of these core new developments.Grammars as formal systems
The hierarchy of grammars
Probabilistic grammars
Finite automata
Push-down automata
Linear-bounded automata
Turing machines
Grammatical inference