Treffer: Compllexity in left-associative grammar
Title:
Compllexity in left-associative grammar
Authors:
Source:
Theoretical computer science. 106(2):283-308
Publisher Information:
Amsterdam: Elsevier, 1992.
Publication Year:
1992
Physical Description:
print, 19 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Intelligence artificielle, Artificial intelligence, Reconnaissance et synthèse de la parole et du son. Linguistique, Speech and sound recognition and synthesis. Linguistics, Automate fini, Finite automaton, Autómata estado finito, Complexité calcul, Computing complexity, Complejidad cálculo, Grammaire CF, Context free grammar, Gramática CF, Grammaire CS, Context sensitive grammar, Gramática CS, Grammaire Chomsky, Chomsky grammar, Gramática Chomsky, Grammaire générative, Generative grammar, Gramática generativa, Grammaire à structure phrase, Sentence structure grammar, Gramática a estructura frase, Langage naturel, Natural language, Lenguaje natural, Méthode récursive, Recursive method, Método recursivo, Structure arborescente, Tree structure, Estructura arborescente, Système informatique, Computer system, Sistema informático, grammaire gauche associative
Document Type:
Fachzeitschrift
Article
File Description:
text
Language:
English
Author Affiliations:
Friedrich-Alexander Univ., 8520 Erlangen, Germany
ISSN:
0304-3975
Rights:
Copyright 1993 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.4666320
Database:
PASCAL Archive
Weitere Informationen
This piper presents a mathematical definition of left-associative grammar, and describes its formal properties. Conceptually, LA-grammar is based on the notion of possible continuations, in contrast to more traditional systems such as phrase structure grammar and categorial grammar, which are linguistically motivated in terms of possible substitutions. It is shown that LA-grammar generates all and only the recursive languages. The Chomsky hierarchy of regular, context-free, and context-sensitive languages is reconstructed in LA-grammar by simulating finite-state automata, pushdown automata, and linearly bounded automata, respectively.