$L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$

Alphabet = { a , b }*

Considering L={WW} is not context free, shouldn't this be non context free as well? otherwise can you provide a machine or grammar which accepts this?


This is a classical example of a context-free language whose complement is not context-free. It is context-free since every word in $w$ has the form $$ \Sigma^i a \Sigma^j \Sigma^i b \Sigma^j = \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j $$ or the similar form with the locations of $a$ and $b$ switched.

| cite | improve this answer | |
  • $\begingroup$ Do you know any source which has drawn the PDA for this language ? or at least the grammar ?! thanks. $\endgroup$ – Richard Jones Sep 26 '17 at 19:23
  • 1
    $\begingroup$ I think you have enough information to work them out yourself. $\endgroup$ – Yuval Filmus Sep 26 '17 at 19:30
  • $\begingroup$ I don't even understand what is that equation you wrote, that doesn't make any sense? $\endgroup$ – Richard Jones Sep 27 '17 at 5:24
  • $\begingroup$ Well, take it as a hint. It's an identity of languages or regular expressions. You can also look for previous instances of your question on this site. $\endgroup$ – Yuval Filmus Sep 27 '17 at 5:41

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