8
$\begingroup$

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

  • 0
    when w1w2ϵ{a,b}*2011-03-02
  • 0
    Do you have any guesses? Is it context-free or not?2011-03-02
  • 0
    i think its not contextfree but i know some similar languages like w1cw2 are contextfree.2011-03-03
  • 0
    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?"2011-05-13
  • 0
    Voting to close as the answer is in a comment.2011-07-12

1 Answers 1

0

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

  • 1
    $S \rightarrow bXa \rightarrow baXba \rightarrow baba$2011-03-14
  • 0
    Of course, Raphael. And you can apply the pumping lemma to the complement, so the language is not context free.2011-03-18
  • 0
    CFL is not closed against complement.2011-03-19