# Non-context-free xcy language.

Excercise from Shallit. Let $L:=\{xcy | x,y\in \{a, b\}^*, y \text{ is a subseq. of } x \}$. Then $L$ is not context free.

Contradics the pumping lemma for context free languages.
Proof. Suppose $L$ is context-free, then there exists $n\geq 1$ such that for every word $w$ with $|w|\geq n$ there exists words $d,x,e,y,f \in \Sigma^*$ such that $|xy| \geq 1, |xey|\leq n$ and $w=dxeyf \in L \iff dx^i e y^i f \in L$ for every $i\geq 0$.

Now pick $w:=a^nb^n c a^n b^n$.

Then $w\in L$. Consider any factorization $dxeyf=w$ s.t. $|xey|\leq n$. We have one of three cases:
1. $xey$ ends exactly in $c$ or at the left of $c$ in $w$.
2. $xey=c$ or $xey$ begins at the left of $c$ in $w$ end ends at the right of $c$ in $w$.
3. $xey$ begins exactly in $c$ or at the right of $c$ in $w$.
Consider the following $i$ values for $d x^i e y^i f$.
Case 1., pick $i:=0$.
Case 2., pick any $i\geq 0$.
Case 3. pick any $i\geq 1$.
Then $d x^i e y^i f\not\in L$ holds for every case. This contradicts the pumping lemma, thus $L$ is not context-free. Q.E.D.