Finite state languages

Noam Chomsky, George A. Miller

Research output: Contribution to journalArticlepeer-review

181 Scopus citations

Abstract

A finite state language is a finite or infinite set of strings (sentences) of symbols (words) generated by a finite set of rules (the grammar), where each rule specifies the state of the system in which it can be applied, the symbol which is generated, and the state of the system after the rule is applied. A number of equivalent descriptions of finite state languages are explored. A simple structural characterization theorem for finite state languages is established, based on the cyclical structure of the grammar. It is shown that the complement of any finite state language formed on a given vocabulary of symbols is also a finite state language, and that the union of any two finite state languages formed on a given vocabulary is a finite state language; i.e., the set of all finite state languages that can be formed on a given vocabulary is a Boolean algebra. Procedures for calculating the number of grammatical strings of any given length are also described.

Original languageEnglish (US)
Pages (from-to)91-112
Number of pages22
JournalInformation and Control
Volume1
Issue number2
DOIs
StatePublished - May 1958
Externally publishedYes

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Finite state languages'. Together they form a unique fingerprint.

Cite this