Context-free languages are not closed under SWAP$(L) = \{ yxz \mid x, y, z \in \Sigma^{*} $ and $ xyz \in L \}$

Question

Currently I am preparing myself for an exam. I was able to show that some languages are closed under certain stuctures. But I'm stucked at the topic, where I have to show that languages are not closed under "certain structures".

As you can read in the headline, Im considering SWAP$(L)$.

Do I know what I have to do? I think I do. I have to find a counterexample where $L$ is context-free and SWAP$(L)$ isn't.

How would I show that $L$ is context-free? I would find a context-free grammar.

How would I show that SWAP$(L)$ is not context-free? My idea would be to use the pumping lemma for context-free languages.

But I have Problems to find a counterexample. I think that I need an expression like " $a^mb^nc^n$, but Im not sure. Can you help me out ?

Thank you for your help and time.

Answer 1

1. If context-free languages are not closed under SWAP, then you can find at least one context-free language $L$ such that SWAP(L) is not context free.

2. Presumably, you will pick $L$ so that the process of proving that SWAP(L) is not context-free is somehow straightforward. It will help to remember a catalogue of some common context-free languages, such as $\{0^a1^a : a\in \mathbb{N}\}$, $\{ww^R : w \in \Sigma^*\}$, $\{0^a1^b0^c : a + 2b =c\}$, and the language of matched parentheses. It will also help to remember a catalogue of languages that are near-miss examples: languages that are not context-free, despite looking similar to a context-free language. Examples include $\{0^a1^a2^a : a\in \mathbb{N}\}$, $\{ww : w\in \Sigma^*\}$, $\{a^mb^n\,c^md^n : m,n\in\mathbb{N}\}$.

3. There are a few ways to prove that a language is not context-free. The usual one is using the pumping lemma: if $L$ is context free, then the pumping lemma applies to it. Hence if the pumping lemma breaks down for $L$, then $L$ is not context free.

   Another approach is to use closure properties: if $L$ is context-free and $R$ is regular, then $L\cap R$ is context-free. Sometimes you can find $R$ such that $L\cap R$ is easy to describe and hence easier to apply the pumping lemma to.

It takes some thinking to find an appropriate context-free language $L$ where SWAP(L) isn't context-free. Here's one way to look at it:

1. The language $L=\{a^m b^m c^n d^n : m,n\in \mathbb{N}\}$ is context-free.

   (Proof: One grammar for it is $S\mapsto PQ,\;\; P\mapsto aPb | \epsilon,\;\; Q\mapsto cQd | \epsilon.$)

2. The similar-looking language $M = \{p^m q^n r^m s^n : m,n\in\mathbb{N}\}$ is not context-free. (Proof: For any pumping length $N$, the string $p^Nq^Nr^Ns^N$ will produce strings outside the language when pumped.)

3. There's a subset of SWAP(L) that looks like M. In fact, it's the intersection of SWAP(L) and the regular language $R=b^*c^*a^*d^*$. The intersection of SWAP(L) and $R$ is the language $\{b^mc^na^md^n : m,n\in \mathbb{N}\}$. We've used a regular language to consider just the swaps of $L$ that take out a perfect chunk of b's and c's and put them before the a's and d's.

4. If SWAP(L) is context-free, then SWAP(L) intersected with $R$ is context-free. But that intersection is essentially the language $M$, which we already know is not context-free. Hence SWAP(L) is not context-free; hence context-free languages are not closed under SWAP.