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!

$\endgroup$
3
  • $\begingroup$ Are you sure this language is actually context free? $\endgroup$
    – sxd
    Jun 27 '12 at 18:15
  • 1
    $\begingroup$ @DimitriSurinx The title reads context-sensitive, and so does look the grammar proposed... $\endgroup$
    – dtldarek
    Jun 27 '12 at 18:17
  • $\begingroup$ Oh, my bad, read over that one! $\endgroup$
    – sxd
    Jun 27 '12 at 18:17
9
$\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$ Jan 7 '14 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
    Jan 7 '14 at 13:41
  • $\begingroup$ You can find a full worked out example here $\endgroup$
    – Mapio
    Feb 20 '19 at 15:58
  • $\begingroup$ @Mapio: The link does not exist anymore $\endgroup$
    – yannis
    Mar 3 '20 at 15:13
  • $\begingroup$ Sorry, here it is the correct one gist.github.com/mapio/c5fe89f55cb6499a743f912b5e53198b $\endgroup$
    – Mapio
    Mar 4 '20 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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