Some questions of language theory
S. ABRAHAM · 1965
It is shown that the assumption that language is non-finite involves the use of a constructive logic which leads to some restrictions on language theory and to the fact that the only possible definition of language is that proposed by generative grammars. Generative grammars can be formulated an normal/Markov/algorithms and thus their study can be reduced to the study of such algorithms of a special type. A new type of generative grammar is defined, called matrix grammar. It is shown that a language generated by a context-restricted grammar can be also generated by a matrix grammar. Some properties of matrix grammars are shown to be decidable. The problem of the explicative power of generative grammars is discussed.