Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

when w1w2ϵ{a,b}* – shervin Mar 2 '11 at 22:46
Do you have any guesses? Is it context-free or not? – Yuval Filmus Mar 2 '11 at 23:14
i think its not contextfree but i know some similar languages like w1cw2 are contextfree. – shervin Mar 3 '11 at 9:22
It is always helpful, to readers, to provide some context or motivation when asking a question. Providing enough background also helps the asker - namely it helps avoid the question "Isn't this homework?" – Sam Nead May 13 '11 at 21:22
Voting to close as the answer is in a comment. – Qiaochu Yuan Jul 12 '11 at 21:38

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

share|cite|improve this answer
$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

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