Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 9 down vote favorite
3

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\}$$

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

closed as too localized by Qiaochu Yuan Jul 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, see the FAQ.

1 Answer

up vote 0 down vote

$$ S \to aSa | bSb | aXb | bXa $$ $$ X \to aXa | bXb | aXb | bXa | \epsilon $$

share|improve this answer
1  
$S \rightarrow bXa \rightarrow baXba \rightarrow baba$ – Raphael Mar 14 '11 at 22:14
Of course, Raphael. And you can apply the pumping lemma to the complement, so the language is not context free. – user8260 Mar 18 '11 at 20:52
CFL is not closed against complement. – Raphael Mar 19 '11 at 13:04
4  
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.