10
$\begingroup$

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!

  • 0
    Are you sure this language is actually context free?2012-06-27
  • 1
    @DimitriSurinx The title reads context-sensitive, and so does look the grammar proposed...2012-06-27
  • 0
    Oh, my bad, read over that one!2012-06-27

2 Answers 2

8

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

  • 2
    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?2014-01-07
  • 1
    @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.2014-01-07
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$.