Context-sensitive grammar for the copy language

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.

• Are you sure this language is actually context free?
– sxd
Jun 27 '12 at 18:15
• @DimitriSurinx The title reads context-sensitive, and so does look the grammar proposed... Jun 27 '12 at 18:17
– sxd
Jun 27 '12 at 18:17

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

• A context-sensitive grammar is defined as all grammars for which every rule has the form $\alpha -> \beta$, with $|\alpha| \leq |\beta|$, but you have the rule $D_2E->F$, is this still a contextsensitive grammar then? Jan 7 '14 at 12:49
• @eager2learn It is not. My example is a kind of a middle step, e.g. the meta-rules don't belong to context-sensitive grammars either. The reason for putting it this way is that it is much cleaner and easier to understand, and still easy/straightforward to transform into a proper context-sensitive grammar. To make the rules obey the $|\alpha|\leq|\beta|$ constraint, one uses the letter-non-terminals (here $A_i$,$B_i$,etc., but not $E$ or $F$) to perform the sorting tasks, i.e. you merge the two symbols into one, e.g. instead of $E$ and $F$ you could use $A_3$/$B_3$ and $A_4$/$B_4$ respectively. Jan 7 '14 at 13:41
• You can find a full worked out example here Feb 20 '19 at 15:58
• @Mapio: The link does not exist anymore Mar 3 '20 at 15:13
• Sorry, here it is the correct one gist.github.com/mapio/c5fe89f55cb6499a743f912b5e53198b Mar 4 '20 at 16:52

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

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!