I need to find a context-sensitive grammar for the copy language $$L = \{ww \; | w \in \{0,1\}^* \}$$
This is what I got so far:
$\begin{eqnarray} S & \Rightarrow & \lambda \; | \; X \\ X & \Rightarrow & 0XA \; | \; 1XB \\ XB & \Rightarrow & CX \\ XA & \Rightarrow & DX \\ CX & \Rightarrow & X0 \\ DX & \Rightarrow & X1 \\ 0X & \Rightarrow & 0 \\ 1X & \Rightarrow & 1 \end{eqnarray}$
This works fine for 0101 but fails even for 00 or 11.
Could you please help me to find a solution?
Thanks in advance!
$\endgroup$ 33 Answers
$\begingroup$A simple way to do this is first create doubled word and then sort it, e.g.
$$\begin{aligned} S &\to D_1D_2T \\ T &\to A_1A_2T \mid B_1B_2T \mid E \\ \alpha_2\beta_1 &\to \beta_1\alpha_2 \\ A_2E &\to E0 \\ B_2E &\to E1 \\ D_2E &\to F \\ A_1F &\to F0 \\ B_1F &\to F1 \\ D_1F &\to \varepsilon \end{aligned}$$ for $\alpha, \beta \in \{A,B,D\}$. Intuitively, it first creates a starter mark $D_1$, then an end-mark of first word $D_2$, and then pairs of letters until the end $E$. The meta-rule sorts all $A_1$ before $A_2$, but without interchanging $A_1$ and $B_1$ or $A_2$ and $B_2$ (and same for $B$s and $D$s). The $E$ stamp renders the $A_2$ and $B_2$ non-terminals and after reaching the middle it changes into $F$ that renders $A_1$ and $B_1$. Finally, after $F$ reaches the begging, it disappears.
Hope that helps ;-)
$\endgroup$ 5 $\begingroup$My idea would be generate in the following manner:
First produce strings of the form $w H \tilde{w}^R E$, where $\tilde{w}^R$ is some "isomorphic" version of the reverse of $w$, say using $A$ instead of $0$ and $B$ instead of $1$, and $E$ is some marker for the end.
Next transform substrings of the form $HA \rightarrow H0$ and $HB \rightarrow H1$.
Next propagate these terminals to the end, or at least until they are to the left of another terminal: $0A \rightarrow A0$, $0B \rightarrow B0$, $1A \rightarrow A1$, $1B \rightarrow B1$, and also $0E \rightarrow E0$, $1E \rightarrow E1$.
Finally, convert $HE \rightarrow \lambda$.
$\endgroup$ $\begingroup$This is not a different answer but just an example for the answer of dtldarek (which I find brillant):
Take for example the word 0101.
Three stages:
1) we add groups of $A_1A_2$ for each 0 and of $B_1B_2$ for each 1 and when we are done we add an $E$:
$S\to D_1D_2T \to D_1D_2A_1A_2T \to D_1D_2A_1A_2B_1B_2T\to D_1D_2A_1A_2B_1B_2E$
2) we apply the $\alpha_2\beta_1 \to \beta_1\alpha_2$ rule as many times as necessary to have all the $*_1$s on the left part of $D_2$ and all the $*_1$s on its right side:
$\to D_1\underline{A_1D_2}A_2B_1B_2E\to D_1A_1D_2\underline{B_1A_2}B_2E \to D_1A_1\underline{B_1D_2}A_2B_2E$
3) starting from the right we get replace all the $A_2$s by 0s and all the $B_2$s by 1s until we arrive to $D_2$ and replace it by an $F$:
$\to D_1A_1B_1D_2A_2E\mathtt{1}\to D_1A_1B_1D_2E\mathtt{01}\to D_1A_1B_1F\mathtt{01}$
and then all the $A_1$s by 0s and all the $B_1$s by 1s:
$\to D_1A_1F\mathtt{101}\to D_1F\mathtt{0101}\to\mathtt{0101}$
and we are done!
$\endgroup$
