Английская Википедия: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 about representing a given context-free language in terms of two simpler languages. These two simpler languages, namely a regular language and a Dyck language, are combined by means of an intersection and a homomorphism.

A few notions from formal language theory are in order. A context-free language is regular, if it can be described by a regular expression, or, equivalently, if it is accepted by a finite automaton. A homomorphism is based on a function <math>h</math> which maps symbols from an alphabet <math>\Gamma</math> to words over another alphabet <math>\Sigma</math>; If the domain of this function is extended to words over <math>\Gamma</math> in the natural way, by letting <math>h(xy)=h(x)h(y)</math> for all words <math>x</math> and <math>y</math>, this yields a homomorphism <math>h:\Gamma^*\to \Sigma^*</math>. A matched alphabet <math>T \cup \overline T</math> is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where <math>T</math> contains the opening parenthesis symbols, whereas the symbols in <math>\overline T</math> contains the closing parenthesis symbols. For a matched alphabet <math>T \cup \overline T</math>, the Dyck language <math>D_T</math> is given by

<math>D_T = \{\,w \in (T \cup \overline T)^* \mid w \text{ is a correctly nested sequence of parentheses} \,\}.</math>

Chomsky–Schützenberger theorem. A language L over the alphabet <math>\Sigma</math> is context-free if and only if there exists

• a matched alphabet <math>T \cup \overline T</math>
• a regular language <math>R</math> over <math>T \cup \overline T</math>,
• and a homomorphism <math>h : (T \cup \overline T)^* \to \Sigma^*</math>

such that <math>L = h(D_T \cap R)</math>.

Proofs of this theorem are found in several textbooks, e.g. Шаблон:Harvtxt or Шаблон:Harvtxt.

References

• Шаблон:Cite book
• Шаблон:Cite book