Article

Free access

Natural languages and the Chomsky hierarchy

Author:

András KornaiAuthors Info & Claims

EACL '85: Proceedings of the second conference on European chapter of the Association for Computational Linguistics

Pages 1 - 7

https://doi.org/10.3115/976931.976932

Published: 27 March 1985 Publication History

Abstract

The central claim of the paper is that NL stringsets are regular. Three independent arguments are offered in favor of this position: one based on parsimony considerations, one employing the McCullogh-Pitts (1943) model of neuruns, and a purely linguistic one. It is possible to derive explicit upper bounds for the number of (live) states in NL acceptors: the results show that finite state NL parsers can be implemented on present-day computers. The position of NL stringsets within the regular family is also investigated: it is proved that NLs are counter-free, but not locally testable.

References

[1]

Angiuin, D. 1981: A note on the number of queries needed to identify regular languages. Information 8 Control 51, 76--87

[2]

Arrow, K. I. 1950: A difficulty in the concept of social welfare. Journal of Political Economy 58, 328--346

[3]

Berwick, R. C. 1982: Computational complexity and Lexocal-Functional Grammar. American Journal of Computational Linguistics 8, 87--108

Digital Library

[4]

Bloomfield, L. 1826: A set of postulates for the science of language. Language 2, 153--164

[5]

Borgida, A. T. 1983: Some formal results about stratificational grammars and their relevance to linguistics. Mathematical Systems Theory 16, 29--56

[6]

Fresnan, J. 1983: The mental representation of grammatical relations (ed) MIT Press, Cambridge, Mass.

[7]

Carroll, J. B. 1953: The study of language. Harvard University Press, Cambridge, Mass.

[8]

Chossky, N. 1957: Syntactic Structures. Mouton. The Hague Chossky, N. 1956: Three models for the description of language. I.R.E. Transactions on Information Theory IT-2.

[9]

Chossky, N. 1961: Some methodological remarks on generative grammar. Word 17, 219--238

[10]

Chossky, N. 1963: Formal properties of grammars. In: Luce-Bush-Galanter (eds) Handbook of mathematical psychology. Wiley, New York

[11]

Chossky, N. 1970: Remarks on nominalization. In: Jacobs-Rosenschein (eds): feedings in English Transformational Grammar. Ginn., Walthas. Mass. 184--221

[12]

Church, K. 1980: On Parsing strategies and closure. Proceedings of the 18th Annual Meeting of the ACL 107--111

Digital Library

[13]

Eilenberg, S. 1974: Automata, languages, and machines. Academic Press, New York

Digital Library

[14]

Gazdar, G. 1982: Phrase structure grammar. In: Jacobson-Pullum (eds): The Nature of Syntactic Representation. Reidel, Dordrecht 131--186

[15]

Greenbaum, J.- R. Cuirk 1970: Elicitation experiments in English: Linguistic studies in usage and attitude. Longman, London

[16]

Greene, J. 1872: Psycholinguistics. Penguin, Harmondsworth

[17]

Harris, Z. 1846: From morpheme to utterance. Language, 22, 161--183

[18]

Harris, Z. 1951: Methods in Structural Linguistics. University of Chicago Press

[19]

Harrison, M. A. 1978: Introduction to Formal Language Theory. Addison-Wesley, Reading, Mass.

Digital Library

[20]

Hockett, C. 1954: Two models of grammatical description. Word 10, 210--231

[21]

Hockett, C. 1955: A manual of phonology. International Journal of American Linguistics, Memoire 11

[22]

Itkonen, E. 1981: The concept of Linguistic intuition. In: Coulsans (ed): A Festschrift for Native Speaker. Mouton, The Hague, 127--140

[23]

Kleene, S. C. 1956: Representation of events in nerve nets and finite automate. In: Shannon - McCarthy (eds): Automata studies. Princeton University Press 3--41

[24]

Lamb, S. M. 1966: Outline of stratificational grammar. Georgetown University Press, Washington D.C.

[25]

Levi-Strauss, C. 1958: Anthropologie structurale. Plon, Parris.

[26]

Lieber, R. 1981: On the Organization of the Lexicon. IULC

[27]

Marcus, S. 1964: Grammatical automata finite. Editure Academiei, Bucharest

[28]

Marks, L. E. 1968 Scaling of grammaticalness of self-embedded English sentences. Verbal Learning & Verbal Behavior 7, 965--867

[29]

Matthews, R. J. 1979: Are the grammatical sentences of a language a recursive set? Synthese 40, 209--224

[30]

McCullogh, W. S. - W. Pitts 1943: A logical calculus of the ideas immanent in nervous activity. Bulletin of mathematical biophysics 5, 115--133

[31]

McNaughton, R. - S. Papert 1968: The syntactic monoid of a regular event. In Arbit (ed): Algebraic theory of machines, languages, and semigroups. Academic Press, New York 297--312

[32]

McNaughton, R - S. Papert 1971: Counter-free automata. Research Monograph no. 65, MIT Press, Cambridge, Mass.

Digital Library

[33]

Miller, G. A. - S. Isard 1964: Free recall of self-embedded English sentences. Information & Control 7, 293--303

[34]

Moore, E. F. 1956: Gedanken-experiments on sequential machines. In: Shannon - McCarthy (eds): Automata studies. Princeton University Press 129--153

[35]

Newayer, F. J. 1980: Linguistic theory in America. Academic Press, New York

[36]

Pullum, G. and G. Gazdar 1982: Natural languages and context free languages. Linguistics and Philosophy 4, 471--504

[37]

Putnam, H. 1961: Some issues in the theory of grammar. Proc. Symposia in Applied Mathematics 1961

[38]

Peich, P. A. 1969: The finiteness of natural languages. Language 45, 831--843

[39]

Robins, R. H. 1959: In defense of BF. Trans. Philol. Soc. 116--144

[40]

Rogers, H. 1967: The theory of recursive functions and effective computability. McGraw-Hill, New York

Digital Library

[41]

Rounds, W. 1975: A grammatical characterisation of exponential-time languages. Proc. 16th Symposium on Switching Theory and Automate 135--143

[42]

Selomaa, A. 1973: Formal Languages. Academic Press, New York

Digital Library

[43]

Sullivan, W. J. 1980: Syntax and Linguistic semantics in stratificational theory. In: Wirth-Moravcaik (eds) Current approaches to syntax. Academic Press, New York 301--327

[44]

Yagve, V. H. 1961: The depth hypothesis. In: Jacobson (ed): Proc. of Symposia in Applied Mathematics 12, 130--138

Cited By

Wurm C(2011)Regular growth automataProceedings of the 12th biennial conference on The mathematics of language10.5555/2050185.2050197(192-208)Online publication date: 6-Sep-2011
https://dl.acm.org/doi/10.5555/2050185.2050197
Yli-jyr?? AKornai ASakarovitch J(2011)Finite-state methods and models in natural language processingNatural Language Engineering10.1017/S135132491100001517:2(141-144)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1017/S1351324911000015
Casacuberta FVidal E(2007)Learning finite-state models for machine translationMachine Language10.1007/s10994-006-9612-966:1(69-91)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1007/s10994-006-9612-9
Show More Cited By

Recommendations

Chomsky Hierarchy And Systolic Y-Tree Automata

We prove that no nonregular deterministic context-free language is accepted by any systolic Y-tree automaton while some of them, but not all, can be accepted by nondeterministic systolic Y-tree automata. We show that weak superstable systolic automata ...
An automata-theoretic characterization of the chomsky-hierarchy
TAMC'10: Proceedings of the 7th annual conference on Theory and Applications of Models of Computation

In this paper a new family of stateless (non-deterministic) pushdown automata are used to accept languages of the Chomsky hierarchy Having only a stack with at most 1 symbol the regular languages can be recognized The usual pushdown automata accept the ...
Refining the hierarchy of blind multicounter languages and twist-closed trios

We introduce the new families (k, r)-RBC of languages accepted in quasi-realtime by one-way counter automata having k blind counters, of which at least r are reversal-bounded. It is proved, that these families form a strict and linear hierarchy of semi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

EACL '85: Proceedings of the second conference on European chapter of the Association for Computational Linguistics

March 1985

284 pages

Conference Chair:
Margaret King
ISSCO

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 27 March 1985

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 100 of 360 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
879
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)13

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wurm C(2011)Regular growth automataProceedings of the 12th biennial conference on The mathematics of language10.5555/2050185.2050197(192-208)Online publication date: 6-Sep-2011
https://dl.acm.org/doi/10.5555/2050185.2050197
Yli-jyr?? AKornai ASakarovitch J(2011)Finite-state methods and models in natural language processingNatural Language Engineering10.1017/S135132491100001517:2(141-144)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1017/S1351324911000015
Casacuberta FVidal E(2007)Learning finite-state models for machine translationMachine Language10.1007/s10994-006-9612-966:1(69-91)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1007/s10994-006-9612-9
Prószéky GTsujii J(1996)Morphological Analyzer as Syntactic ParserProceedings of the 16th conference on Computational linguistics - Volume 210.3115/993268.993381(1123-1126)Online publication date: 5-Aug-1996
https://dl.acm.org/doi/10.3115/993268.993381
Goldberg JKálmán LZampolli A(1992)The first BUG reportProceedings of the 14th conference on Computational linguistics - Volume 310.3115/993079.993104(945-949)Online publication date: 23-Aug-1992
https://dl.acm.org/doi/10.3115/993079.993104
Goldberg JKálmán LZampolli A(1992)The first BUG reportProceedings of the 14th conference on Computational linguistics - Volume 310.3115/992383.992408(945-949)Online publication date: 23-Aug-1992
https://dl.acm.org/doi/10.3115/992383.992408

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten