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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s