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

  • 0
    CFL is not closed against complement.2011-03-19