Chomsky–Schützenberger Theorem

languages

Definition

Chomsky–Schützenberger Theorem

Let Let $D_n$ over ${\Gamma }_n$ be a Dyck language.

A language $L$ over $\Sigma$ is context-free iff there exists some $n\ge 0$ and a homomorphism $h:{\Gamma }_n^{\ast }\to {\Sigma }^{\ast }$ such that:

$$L=h(D_n\cap R)$$

where $R$ denotes a regular language over ${\Gamma }_n$.

Choosing n

When to choose $D_n$

Choose $n$ according to how many independent matching patterns you want to encode.

• $L_1=\{x{x}^r\mid x\in \{a,b{\}}^{+}\}$: use $D_1$. One kind of matching is enough for one mirrored block.
• $L_2=\{x{x}^{r}y{y}^r\mid x,y\in \{a,b{\}}^{+}\}$: use $D_2$. Two independent mirrored blocks suggest two bracket types.
• $L_3=\{x{x}^{r}y{y}^{r}z{z}^r\mid x,y,z\in \{a,b{\}}^{+}\}$: use $D_3$. Three independent mirrored blocks suggest three bracket types.
• $L_4=\{x{x}^{r}y{y}^{r}z{z}^{r}t{t}^r\mid x,y,z,t\in \{a,b{\}}^{+}\}$: use $D_4$. Four independent mirrored blocks suggest four bracket types.

Some less obvious examples are:

• $L=\{a^n{b}^m{c}^n{d}^m\mid n,m\ge 0\}$: a natural choice is $D_2$. The language has two independent matching conditions, even though they are not written as explicit reversals.
• $L=\{wc{w}^r\mid w\in \{a,b{\}}^{\ast }\}$: a natural choice is $D_1$. The middle marker $c$ separates the two halves, so one bracket type already suffices.
• $L=\{uv{u}^r{v}^r\mid u,v\in \{a,b{\}}^{\ast }\}$: a natural choice is $D_2$. There are two nested dependencies, but they are not presented as the same kind of mirror image.
• $L=\{\text{properly nested expressions with }(,),[,]\}$: a natural choice is $D_2$. Two bracket types are needed to distinguish the two kinds of delimiters.

The choice is not unique. It is often just the most natural encoding for the proof.

Examples

Example 1

$$L=\{a^n{b}^n\mid n\ge 0\}=h(D_1\cap \{({\}}^{\ast }\{){\}}^{\ast })$$

where $h:\{(,){\}}^{\ast }\to \{a,b{\}}^{\ast }$ with $h(()=a$ and $h())=b$.

Therefore, $L$ is context-free.

Example 2

Consider the language $L=h(D_k\cap R)$ with $k=2$ and

$$h:\{(,[,],){\}}^{\ast }\to \{a,b,c{\}}^{\ast }$$

where

$$h(()=a,h([)=b,h(])=c,h())=c.$$

Here, $h$ need not be bijective: two different bracket symbols may map to the same terminal symbol, as $]$ and $)$ both map to $c$.

The regular language is

$$R=\{(,[{\}}^{\ast }\{),]{\}}^{\ast }.$$

Then, for example,

$$abcccc\in L\text{and}aababcccc\in L.$$

$\{x{x}^{r}y{y}^r\mid x,y\in \{a,b{\}}^{+}\}$

Let $L=\{x{x}^{r}y{y}^r\mid x,y\in \{a,b{\}}^{+}\}$. We have to find a Dyck language $D_n$, a regular language $R$, and a string homomorphism $h$, such that:

$$L=h(D_n\cap R)$$

Choose $n=2$ with $D_2$, and $h$ with:

$$\begin{array}{rl}h(()& =h())=a\\ h([)& =h(])=b\end{array}$$

Now, we have to ensure that the bracket structure for $x$ and $y$ exists. We choose $R$:

$$R=(\{(,[{\}}^{+}\cdot \{),]{\}}^{+})\cdot (\{(,[{\}}^{+}\cdot \{),]{\}}^{+})$$

$\{x{x}^{r}y{y}^r\mid x,y\in \{a,b{\}}^{+}\}$

Let $L=\{x{x}^{r}y{y}^r\mid x,y\in \{a,b{\}}^{+}\}$. We have to find a Dyck language $D_n$, a regular language $R$, and a string homomorphism $h$, such that:

$$L=h(D_n\cap R)$$

We first have to choose $n$ for $D_n$. Each $w\in L$ has two structural dependencies $x{x}^r$ and $y{y}^r$. Thus, we choose $n=2$.

Next, we choose a regular language $R$ that gives $D_2\cap R$ shape constraints. We choose:

$$R=\underset{x{x}^r\text{ dependency}}{\underbrace{(\{(,]{\}}^{+}\cdot \{),]{\}}^{+})}}\cdot \underset{y{y}^r\text{ dependency}}{\underbrace{(\{(,[{\}}^{+}\cdot \{),]\}+)}}$$

Malformed $R$ Note that $R$ itself allows for malformed bracket expressions, such as:

$$(],(]],([]),\dots$$

That’s why we intersect with $D_2$, the set of all well-formed bracket expressions.

Next, we have to select a string homomorphism $h$ that maps each word $w_r\in R$ to a word $w_{\sigma }\in {\Sigma }^{\ast }=\{a,b{\}}^{\ast }$. Given our $R$, a natural choice $h$ is:

$$\begin{array}{rl}h(()& =h())=a\\ h([)& =h(])=b\end{array}$$

Possible mapping to $aabb\in L$

$$h(()[])=aabb$$

Forbidden due to $R$'s shape constraints

$$h(([]))=abba$$

We found a valid $⟨D_n,R,h⟩$ combination. Therefore, $L$ is context-free.

$\{w{c}^n\mid w\in \{a,b{\}}^{\ast },|w|\ge n\}$

Let $L=\{w{c}^n\mid w\in \{a,b{\}}^{\ast },|w|\ge n\}$. We have to find a Dyck language $D_n$, a regular language $R$, and a string homomorphism $h$, such that:

$$L=h(D_n\cap R)$$

$n=1$ We try $n=1$ and thus $D_1$. We have to find a $R$ that forms the shape of the dependencies.

$$R=\{({\}}^{+}\cdot \{){\}}^{+}=\{(),((),()),\dots \}$$

For $h$, we choose:

$$\begin{array}{rl}h(()& =a\\ h())& =c\end{array}$$

Therefore:

$$\begin{array}{rl}{D}_1\cap R& =\{{(}^m{)}^m\mid m\ge 1\}\\ h(D_1\cap R)& =\{a^m{c}^m\mid m\ge 1\}\end{array}$$

Problems:

• We cannot express the entire alphabet $\Sigma =\{a,\underline{b}\}$ via $h(D_1\cap R)$.
• We strictly enforced equality in length, i.e. $|w|=n$, but $L$ specifies $|w|\ge n$.

$n=2$ Given that $n=1$ types of brackets aren't enough, we increase $n$ to $n=2$ and choose $R$:

$$R=\{(,[{\}}^{+}\cdot \{),]{\}}^{+}$$

We then choose $h$:

$$\begin{array}{rl}h(()& =a\\ h([)& =b\\ h())=h(])& =c\end{array}$$

To evaluate $D_2\cap R$, we must ensure that the sequence of closing brackets is the exact structural mirror of the opening brackets. Let $w^r$ denote the string reversal of $w$, and let $\overline{x}$ denote a character mapping where $\overline{(}=)$ and $\overline{[}=]$.

$$\begin{array}{rl}{D}_2\cap R& =\{w\overline{w^r}\mid w\in \{(,[{\}}^{+}\}\\ h(D_2\cap R)& =\{w{c}^{|w|}\mid w\in \{a,b{\}}^{+}\}\end{array}$$

Problem: We still strictly enforce $|w|=n$ rather than $|w|\ge n$.

$n=3$ To solve the inequality $|w|\ge n$, we must distinguish between two structural roles for the characters in our prefix $w$:

1. Counted characters: These generate a corresponding $c$ in the suffix.
2. Extra characters: These do not generate a $c$ (they map to $\epsilon$ under $h$).

Since our prefix alphabet is $\{a,b\}$, every character generated in $w$ requires two independent choices: its letter ($a$ or $b$) and its structural role (counted or extra). This results in $2\times 2=4$ distinct states:

1. Counted $a$
2. Counted $b$
3. Extra $a$
4. Extra $b$

A string homomorphism $h$ is strictly deterministic; one bracket type can only map to one specific output. If we choose $n=3$, the Dyck language $D_3$ only provides $3$ distinct pairs of brackets. By the pigeonhole principle, we cannot map $4$ independent states to $3$ bracket pairs.

If we try $n=3$, we are forced to sacrifice a combination (e.g., we could generate extra $a$‘s, but not extra $b$‘s). Therefore, $n=3$ fails, and we must increase the dimension to $n=4$.

$n=4$ We choose $R$ as:

$$R=\{{(}_1,{(}_2,{(}_3,{(}_4{\}}^{\ast }\cdot \{{)}_1,{)}_2,{)}_3,{)}_4{\}}^{\ast }$$

Note: We use the Kleene star to allow for $n=0$ and $w=\epsilon$.

We have to consider the following dependencies:

• $a$ or $b$ extra (no $c$ generated at the end)
• $a$ or $b$ counted (one $c$ generated at the end)

We then construct $h$ mapping all opening brackets to our prefix alphabet, and erasing the closing brackets of the “extra” characters:

$$\begin{array}{rlrl}h({(}_1)& =a& h({)}_1)& =\epsilon \text{(extra }a\text{)}\\ h({(}_2)& =b& h({)}_2)& =\epsilon \text{(extra }b\text{)}\\ h({(}_3)& =a& h({)}_3)& =c\text{(counted }a\text{)}\\ h({(}_4)& =b& h({)}_4)& =c\text{(counted }b\text{)}\end{array}$$

Therefore, let $w_{open}$ be an arbitrary sequence of opening brackets, $w_{open}^r$ be its reversal, and $\overline{x}$ be the mapping to closing counterparts:

$$\begin{array}{rl}{D}_4\cap R& =\{w_{open}\overline{w_{open}^r}\mid w_{open}\in \{{(}_1,{(}_2,{(}_3,{(}_4{\}}^{\ast }\}\\ h(D_4\cap R)& =\{h(w_{open}\overline{w_{open}^r})\mid w_{open}\in \{{(}_1,{(}_2,{(}_3,{(}_4{\}}^{\ast }\}\end{array}$$

For every word evaluated by $h$, the prefix $w_{open}$ generates $|w_{open}|$ characters of $a$ and $b$. The suffix $\overline{w_{open}^r}$ generates exactly $n$ characters of $c$ (where $n$ is the number of counted brackets) and $|w_{open}|-n$ empty strings $\epsilon$.

Since $|w_{open}|\ge n$ is always structurally guaranteed, this perfectly yields

$$L=\{w{c}^n\mid w\in \{a,b{\}}^{\ast },|w|\ge n\}$$

proving $L$ is a context-free language.