1
$\begingroup$

Possible Duplicate:
Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free

Do there exist context-free grammars for the following two languages:

  1. The set of all strings of the form $xx$ where $x$ is a sequence of $0$'s and $1$'s. (For instance $0110101101$.)

  2. The set of all strings of the form $xy$ where $x$ and $y$ are sequences of $0$'s and $1$'s, $x$ and $y$ have the same length and $x\neq y$.

$\endgroup$
  • 1
    $\begingroup$ Another example where cs.stackexchange is used as a "help desk" for students who don't feel like solving their assignments and ask us to do it for them. I have no problem with giving hints, but full solutions should IMHO be discouraged. $\endgroup$ – Yuval Filmus Jan 31 '13 at 0:26
  • $\begingroup$ @YuvalFilmus We do discourage them, but we can hardly do more. Please discontinue using comments for this; if you have a meta issue, use Computer Science Meta. $\endgroup$ – Raphael Jan 31 '13 at 9:41
  • 1
    $\begingroup$ The first is utterly standard and not worth answering without any indication of effort on your part (in particular, it is covered in (almost) every resource on context-free langauge). The second has been answered; closing as duplicate. $\endgroup$ – Raphael Jan 31 '13 at 9:44