Context-sensitive grammar for the copy language

Question

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!

Answer 1

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 ;-)

Answer 2

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$.