Formal Languages: Origins and Directions
- 1 January 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Annals of the History of Computing
- Vol. 3 (1) , 14-41
- https://doi.org/10.1109/mahc.1981.10006
Abstract
Origins of the theory of formal languages and automata are surveyed starting from 1936 with the work of Turing and Post. Special attention is given to the machine translation projects of the 1950s and early 1960s and associated work in mathematical linguistics. The development of the Chomsky hierarchy of grammars, machines, and languages from 1956 to 1964 is traced. It is observed that the same important ideas emerged independently for the automatic analysis and translation of both natural and artificial languages. Since 1964, formal language theory is part of theoretical computer science. A few of the directions since 1964 are considered: restrictions and extensions of context-free grammars and pushdown store automata, unifying frameworks, and complexity questions.Keywords
This publication has 100 references indexed in Scilit:
- Mathematical models for cellular interactions in development I. Filaments with one-sided inputsPublished by Elsevier ,2004
- Context-free grammar formsJournal of Computer and System Sciences, 1975
- Uniformly erasable AFLJournal of Computer and System Sciences, 1975
- General context-free recognition in less than cubic timeJournal of Computer and System Sciences, 1975
- On tape-bounded complexity classes and multihead finite automataJournal of Computer and System Sciences, 1975
- Strict deterministic grammarsJournal of Computer and System Sciences, 1973
- Quasi-realtime languagesTheory of Computing Systems, 1970
- Control sets on grammarsTheory of Computing Systems, 1968
- A note on undecidable properties of formal languagesTheory of Computing Systems, 1968
- Nonerasing stack automataJournal of Computer and System Sciences, 1967