### closure properties

Once you have a small collection of non-context-free languages, you can often use closure properties of $ mathrm {CFL} $ as follows:

For example, $ L in mathrm {CFL} $. Then through Closure property X (together with Y) $ L & # 39; in mathrm {CFL} $. This contradicts $ L & # 39; notin mathrm {CFL} $, which we know to contain $ L notin mathrm {CFL} $.

This is often shorter (and often less error prone) than using any of the other results that require less prior knowledge. It is also a general concept that can be applied to all types of object classes.

**Example 1:** *Overlap with regular languages*

We note $ mathcal L (e) $ the regular language specified by a regular expression $ e $.

Let $ L = {w midw in {a, b, c } ^ *, | w | _a = | w | _b = | w | _c } $. How

$ qquad displaystyle L cap mathcal {L} (a ^ * b ^ * c ^ *) = {a ^ nb ^ nc ^ n in mathbb {N} } notin mathrm {CFL} $

and $ mathrm {CFL} $ is closed at the intersection with regular languages, $ L notin mathrm {CFL} $.

**Example 2:** *(Inverse) homomorphism*

Let $ L = {(ab) ^ {2n} c ^ md ^ {2n-m} (aba) ^ {n} mid m, n in mathbb {N} } $. With the homomorphism

$ qquad displaystyle phi (x) = begin {cases}

a & x = a \

varepsilon & x = b \

b & x = c lor x = d

end {cases} $

we have $ phi (L) = {a ^ {2n} b ^ {2n} a ^ {2n} mid n in mathbb {N} }. $

Now with

$ qquad displaystyle psi (x) = begin {cases}

aa & x = a lor x = c \

bb & x = b

end {cases} quad text {and} quad L_1 = {x ^ nb ^ ny ^ n mid x, y in {a, c } wedge n in mathbb {N} }, $

we get $ L_1 = psi ^ {- 1} ( phi (L))) $.

Finally, when we cross $ L_1 $ with the regular language $ L_2 = mathcal L (a ^ * b ^ * c ^ *) $, we get the language $ L_3 = {a ^ nb ^ nc ^ n mid n in mathbb {N} } $.

Altogether we have $ L_3 = L_2 cap psi ^ {- 1} ( phi (L)) $.

Now suppose that $ L $ was context-free. Then, since $ mathrm {CFL} $ is locked against homomorphism, inverse homomorphism, and intersection with regular sets, $ L_3 $ is also context-free. But we *knows* (possibly via pumping lemma) that $ L_3 $ is not context-free, so this is a contradiction. We have shown that $ L notin mathrm {CFL} $.

### Exchange lemma

The *Exchange lemma* (1) proposes a necessary condition for context freedom that is even stronger than Ogden's lemma. For example, it can be used to show this

$ qquad {xyyz mid x, y, z in {a, b, c } ^ + } notin mathrm {CFL} $

that resists many other methods. This is the lemma:

Leave $ L in mathrm {CFL} $. Then there is a constant $ c_L $ such that for every integer $ n geq 2 $, every set $ Q_n subseteq L_n = L cap Sigma ^ n $ and every integer $ m $ with $ n geq m geq holds 2 $ There are $ k geq frac {| Q_n |} {c_L n ^ 2} $ strings $ z_i in Q_n $ with

- $ z_i = w_ix_iy_i $ for $ i = 1, dots, k $,
- $ | w_1 | = | w_2 | = dots = | w_k | $,
- $ | y_1 | = | y_2 | = dots = | y_k | $,
- $ m geq | x_1 | = | x_2 | = dots = | x_k | > frac {m} {2} $ and
- $ w_ix_jy_i in L_n $ for all $ (i, j) in (1..k) ^ 2 $.

Applying it means finding $ n, m $ and $ Q_n $ such that 1.-4. but keep 5th is hurt. The application example in the original work is very detailed and is therefore omitted here.

*Currently, I have no freely available reference and the above formulation comes from a preprint of (1) from 1981. I am grateful for finding better references. It seems that the same property has been (re) discovered recently (2).*

### Other necessary conditions

Boonyavatana and Slutzki (3) investigate several conditions that are similar to Pumping and Interchange Lemma.

- An "Interchange Lemma" for context-free languages by W. Ogden, R. J. Ross and K. Winklmann (1985)
- Exchange of Lemmas for Regular and Context Free Languages by T. Yamakami (2008)
- The Exchange or Pump (DI) Lemmas for Context Free Languages by R. Boonyavatana and G. Slutzki (1988)