On certain formal properties of grammars

Research output: Contribution to journalArticlepeer-review

653 Scopus citations

Abstract

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
Volume2
Issue number2
DOIs
StatePublished - Jun 1959
Externally publishedYes

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

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

Cite this