TY - JOUR

T1 - Finite state languages

AU - Chomsky, Noam

AU - Miller, George A.

N1 - Funding Information:
In the vast majority of communication situations the messages that are exchanged consist of strings of symbols. It is possible to imagine a code that uses only one symbol per message, but few situations are so * This work was supported in part by the Army (Signal Corps), the Navy (Office of Naval Research), the Air Force (Office of Scientific Research and Operational Applications Laboratory, Air Research and Development Command), the National Science Foundation, and the Social Science Research Council (Committee on Mathematical Training of Social Scientists), and appears as report number AFCRC-TR-58-50, ASTIA Document Number AD 146781.

PY - 1958/5

Y1 - 1958/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=5244228754&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=5244228754&partnerID=8YFLogxK

U2 - 10.1016/S0019-9958(58)90082-2

DO - 10.1016/S0019-9958(58)90082-2

M3 - Article

AN - SCOPUS:5244228754

VL - 1

SP - 91

EP - 112

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 2

ER -