# is this language context free? [closed]

I need an NPDA for the following language if it is context-free, and if it isn't I need a proof using the pumping lemma that it is not a CFL:

$$L_1=\{w_1w_2 \in \{a,b\}^* : |w_1| = |w_2|,w_1\neq w_2\}$$

-

## closed as too localized by Qiaochu YuanJul 12 '11 at 21:37

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

When is it due :-)? –  Aryabhata Mar 2 '11 at 22:38
when w1w2ϵ{a,b}* –  shervin Mar 2 '11 at 22:46
If it's homework, could you please tag it as such? –  Yuval Filmus Mar 2 '11 at 23:52
it's not homework. –  shervin Mar 3 '11 at 9:22
If it is not homework, why does it have to be Pumping Lemma? –  Raphael Mar 14 '11 at 22:11

$$S \to aSa | bSb | aXb | bXa$$ $$X \to aXa | bXb | aXb | bXa | \epsilon$$
$S \rightarrow bXa \rightarrow baXba \rightarrow baba$ –  Raphael Mar 14 '11 at 22:14
I found the answer,its context free: $$S \to UV | VU$$ $$U \to aUa | bUb | aUb | bUa | a$$ $$V \to aVa | bVb | aVb | bVa | b$$ -special thanks to kaveh for support. –  shervin Mar 20 '11 at 19:17