Possible Duplicate:
Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free
Can anyone prove that the following is a CFL? or not? why?
$$L=\{w=w_1w_2 \mid len(w_1)=len(w_2) \mbox{ and $w_1$ does not equal $w_2$}\}$$
0
$\begingroup$
$\endgroup$
marked as duplicate by A.Schulz, Pål GD, Merbs, Raphael♦ Jan 28 '13 at 10:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
migrated from cstheory.stackexchange.com Jan 27 '13 at 12:46
This question came from our site for theoretical computer scientists and researchers in related fields.
-
$\begingroup$ What have you tried? Have you tried making a PDA? Do you know the pumping lemma for CFLs? $\endgroup$ – Pål GD Jan 27 '13 at 13:43
2
$\begingroup$
$\endgroup$
This must be a classic in formal language theory. The Pumping Lemma will not help, because, unexpectedly, it is context-free. (I did not see the answer here, but it might be overlooked)
The $w_1$ and $w_2$ parts must have a position where they differ. Unfortunately, we cannot distinguish the middle and the two matching positions at the same time. However, we can find matching positions without knowing the middle.
With some effort you can convince yourself that your language $L$ equals $$\{ x_1 a x_2 b x_3 \mid a,b \in \Sigma, a\neq b, |x_1|+|x_3| = |x_2| \}.$$ Once you have shown that, write a grammar using that formulation.
-
$\begingroup$ This is a great idea to convert that language to an equivalent one but could you please explain more? and how did that inspired?! <br> at last i was not able to say that, this is CFG or not $\endgroup$ – user6581 Jan 27 '13 at 16:43
-
$\begingroup$ Dear @Saman, the question has now been marked as duplicate. At the start of the question you will find a link to the earlier occurrence. It seems to have more detailed suggestions. Have a look. $\endgroup$ – Hendrik Jan Jan 28 '13 at 18:33
