On certain formal properties of grammars

Research output: Contribution to journalArticlepeer-review

767 Scopus citations


A grammar can be regarded as a device that enumerates the sentences of a language. We study a sequence of restrictions that limit grammars first to Turing machines, then to two types of system from which a phrase structure description of the generated language can be drawn, and finally to finite state Markov sources (finite automata). These restrictions are shown to be increasingly heavy in the sense that the languages that can be generated by grammars meeting a given restriction constitute a proper subset of those that can be generated by grammars meeting the preceding restriction. Various formulations of phrase structure description are considered, and the source of their excess generative power over finite state sources is investigated in greater detail.

Original languageEnglish (US)
Pages (from-to)137-167
Number of pages31
JournalInformation and Control
Issue number2
StatePublished - Jun 1959
Externally publishedYes

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'On certain formal properties of grammars'. Together they form a unique fingerprint.

Cite this