$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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Cross-posted: cs.stackexchange.com/q/81708/755, math.stackexchange.com/q/2446349/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$– D.W. ♦Commented Sep 27, 2017 at 0:57
-
$\begingroup$ @TeamBright please do not edit closed questions, if you add LaTeX support, the question gets bumped to reopen queue. After your edit the queston is still duplicate. $\endgroup$– EvilCommented Oct 12, 2017 at 19:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Sep 26, 2017 at 18:03
-
$\begingroup$ Do you know any source which has drawn the PDA for this language ? or at least the grammar ?! thanks. $\endgroup$ Commented Sep 26, 2017 at 19:23
-
1$\begingroup$ I think you have enough information to work them out yourself. $\endgroup$ Commented Sep 26, 2017 at 19:30
-
$\begingroup$ I don't even understand what is that equation you wrote, that doesn't make any sense? $\endgroup$ Commented Sep 27, 2017 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$ Commented Sep 27, 2017 at 5:41