In
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet".
The alphabet of a formal language consists of symbol ...
, the Chomsky–Schützenberger theorem may refer to either of two different theorems derived by
Noam Chomsky
Avram Noam Chomsky (born December 7, 1928) is an American professor and public intellectual known for his work in linguistics, political activism, and social criticism. Sometimes called "the father of modern linguistics", Chomsky is also a ...
and
Marcel-Paul Schützenberger
Marcel-Paul "Marco" Schützenberger (24 October 1920 – 29 July 1996) was a French mathematician and Doctor of Medicine. He worked in the fields of formal language, combinatorics, and information theory.Herbert Wilf, Dominique Foata, ''et al.'', ...
concerning
context-free language
In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, mos ...
s:
*The
Chomsky–Schützenberger enumeration theorem about the number of words of a given length generated by an unambiguous context-free grammar
*The
Chomsky–Schützenberger representation theorem In formal language theory, the Chomsky–Schützenberger representation theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger in 1959 about representing a given context-free language in terms of two simpler languages. Thes ...
representing any context-free language by a combination of a regular language and a Dyck language
{{mathdab