11
$\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!

$\endgroup$
3
  • $\begingroup$ Are you sure this language is actually context free? $\endgroup$
    – sxd
    Commented Jun 27, 2012 at 18:15
  • 1
    $\begingroup$ @DimitriSurinx The title reads context-sensitive, and so does look the grammar proposed... $\endgroup$
    – dtldarek
    Commented Jun 27, 2012 at 18:17
  • $\begingroup$ Oh, my bad, read over that one! $\endgroup$
    – sxd
    Commented Jun 27, 2012 at 18:17

3 Answers 3

10
$\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
  • 2
    $\begingroup$ 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? $\endgroup$ Commented Jan 7, 2014 at 12:49
  • 1
    $\begingroup$ @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. $\endgroup$
    – dtldarek
    Commented Jan 7, 2014 at 13:41
  • 1
    $\begingroup$ You can find a full worked out example here $\endgroup$
    – Mapio
    Commented Feb 20, 2019 at 15:58
  • $\begingroup$ @Mapio: The link does not exist anymore $\endgroup$
    – yannis
    Commented Mar 3, 2020 at 15:13
  • $\begingroup$ Sorry, here it is the correct one gist.github.com/mapio/c5fe89f55cb6499a743f912b5e53198b $\endgroup$
    – Mapio
    Commented Mar 4, 2020 at 16:52
2
$\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$
0
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .