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