Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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... – dtldarek Jun 27 '12 at 18:17
Oh, my bad, read over that one! – sxd Jun 27 '12 at 18:17
up vote 8 down vote accepted

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

share|cite|improve this answer
great illustration, thank you! – muffel Jun 27 '12 at 21:32
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? – eager2learn 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. – dtldarek Jan 7 '14 at 13:41

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.