Re: history of generative grammars
- From: Peter Asveld <infprja@xxxxxxxxxxxxx>
- Date: Tue, 20 Mar 2007 15:52:37 +0000 (UTC)
In comp.theory Helmut Richter <hhr-m@xxxxxx> wrote:
[Followup-To: comp.theory]
There are several sciences in which generative grammars for producing
languages can play a role. I would like to learn something on the
historical background. (I am not at all interested in the question
whether it is a good or bad idea to use such grammars, which, for some
fields, is debated.)
The phenomenon I am talking about is:
1. There is a device of some mathematical nature, or of a nature that
could easily be described in mathematical terms, which describes
the syntax to which the members a set of symbol chains adhere. The
existence of a decision procedure (whether a text adheres to the
syntax) is welcomed but not mandatory.
2. The resulting set is understood as the set of the syntactically
valid sentences of a language and is therefore - a bit sloppily -
called a "language".
I see mainly four areas of interest where such formal or mathematical
grammars are used:
Mathematical logic: I think it was Hilbert who formally described the
set of terms and formulas in which deductions can be made. The term
"language" which is used today for this concept seems to be much
newer. For instance in Kleene's "Introduction to Metamathematics", he
uses the term "language" in the explanations but would not call the
result of his formal definitions a language but rather a "formal
system".
Don't forget the work of E.L. Post; Chomsky grammars are to an certain
extend based on his ideas.
Linguistics: The use of formal grammars to describe syntactic
structures of natural languages is due to Chomsky. He invented it in
order to corroborate his theory of innate language structures in the
brain. Both this theory and its alleged corroboration by generative
grammars have remained controversial (but this is not my current
interest).
Mathematics, theoretical computer science: Word problems, for instance
in group theory, have been investigated since about 1910, but have not
been connected to languages. The advent of computers and computer
languages in the late 1950ies have aroused interest in the
mathematical properties of such languages, with many results mainly
for the small subclass of grammars that is used in compilers. Also,
some (un)decidability results on language classes have been found.
Don't forget Axel Thue.
Applied computer science: Since 1960, generative grammars are the
standard device for specifying the syntax of computer languages,
particularly in standards documents.
I would add another category:
Biology: Lindenmayer systems, parallel rewriting.
If we put the whole history together, we obtain the following picture:
- Mathematical investigations on (what we call now) formal grammars
have remained without impact on other fields, mainly because the
language classes were not suited for applications elsewhere.
- Logicians used a formal (or easily to formalise) language in order
to be able to talk about deductions - for instance Gödel's work
would have been impossible without -, but they were not interested
in other grammars for other languages.
- Chomsky published his ideas on generative grammars.
- Some computer people (Backus, Naur) found context-free
grammars particularly useful for describing computer languages; in
the sequel efficient parsing algorithms for a subset of the
context-free grammars were invented.
- After so much interest in formal languages, logicians used the term
"language" for what they had formerly called "formal systems".
Now my questions to the group:
- Is this a good overall picture? Is it factually correct?
- What important things have I forgot? (What about the early "computer
linguists" like Bar-Hillel: where does their work fit in the picture?
What about regular languages (Moore, Mealy, Kleene)?)
Don't forget the paper by N. Chomsky & M.P. Schuetzenberger: it resulted
in numerous papers on context-free languages, regular languages, formal
power series, weighted grammars, weighted automata, fuzzy grammars, etc.
E.g., weighted grammars, weighted automata, and corresponding algorithms
have been applied in automatic speech recognition.
- Is it true that there is only one spot in history where linguists
and mathematicians have met: when the latter took over the term
"context-free" from the former, nearly without any results beyond
the mere definitions?
In the early 1990's there was second spot (``Mildly context-sensitive
languages'', A.K. Joshi, K. Vijay-Shanker, D. Weir); see e.g.
K. Vijay-Shanker & D.J. Weir: The equivalence of four extensions of
context-free grammars, Math. Systems Theory 27 (1994) 511-546.
- Is it true that neither in linguistics nor in computer science any
type of grammar more general than context-free has ever played a
practical role?
These mildly context-sensitive languages are located properly in between
the context-free and the context-sensitive languages.
Lindenmayer systems have been used to model growth of plants and in
computer graphics.
Formal languages and grammars is just one side of the coin; the other
side is formal languages and automata/machines/acceptors which lead
to notions like (un)decidability, P, NP and NP-completeness, efficiency
[The latter ones have had an enormous impact in applied mathematics,
OR, combinatorics, etc.] The finite-state concept (automata) plays
a major part in very practical matters like verification and testing
of embedded systems.
More on the early history of formal languages is in
S.A. Greibach, Formal languages: origins and directions, Ann. Hist. Comput.
3 (1981) no.1, 14-41.
A. Nijholt, Computers and languages: theory and practice (1988),
North-Holland, Amsterdam ISBN 0-444-70463-9
--
Helmut Richter
HTH
Peter Asveld
---------------------------------------------------------------------------
Peter R.J. Asveld, e-mail: X@Y X=infprja Y=cs.utwente.nl
Dept. of Computer Science, Twente University of Technology, P.O. Box 217,
7500 AE Enschede, The Netherlands. http://wwwhome.cs.utwente.nl/~infprja/
.
- Prev by Date: Re: history of generative grammars
- Next by Date: Re: Hoare's triples question
- Previous by thread: Re: history of generative grammars
- Index(es):
Relevant Pages
|
