Context Sensitive Grammar for $x \# x^R \# x$

Question

This language is given.

$L = \{\; x \# x^R \# x \mid x\in \{a,b\}^*\;\}$

I have to figure out a context sensitive grammar for it.

I've tried several rules already but it's hard to make a copy of the first part and also get it in the last with the reversed part in the middle.

Answer 1

A context-sensitive grammar

$$\begin{aligned} S&\to AS\alpha\alpha \mid BS\beta\beta \mid \#T & & (1)\\ A\alpha&\to\alpha A &&(2)\\ B\alpha&\to\alpha B &&(3)\\ A\beta&\to\beta A &&(4)\\ B\beta&\to\beta B &&(5)\\ T\alpha\alpha&\to ATA&&(6)\\ T\beta\beta&\to BTB&&(7)\\ A&\to a&&(8)\\ B&\to b&&(9)\\ T&\to\# &&(10)\\ \end{aligned}$$

OK, I am lying. Except context-free rules $1$, $8$, $9$, $10$, none of the rules are allowed in a context-sensitive grammar.

However, those rules are non-contracting. They can be transformed methodically to context-sensitive rules as shown here. Hence, we can say the non-contracting grammar above represents a context-sensitive grammar.

The idea to generate $L$: blowup, move and change

An effective approach is to design grammar rules in the following order.

1. Blow up the initial symbol to include the field separators and enough placeholders.
2. Move the placeholders to the appropriate destinations.
3. At destinations, change placeholders to wanted symbols.

Employ new symbols as well as left-and/or-right context to ensure orderly derivations and no unintended derivations.

Suppose we have derived $\chi\#\chi^RT\chi$ for some string $\chi$ consisting of $A$s and $B$s. Here is how we can extend $\chi$ in $\chi\#\chi^RT\chi$ to $A\chi$.

1. Surround it by $\color{blue}{A}\cdots\color{blue}{\alpha\alpha}$ so that we will derive $\color{blue}{A}\chi\#\chi^RT\chi\color{blue}{\alpha\alpha}$.
2. Move $\color{red}{\alpha\alpha}$ towards $T$ to obtain ${A}\chi\#\chi^RT\color{red}{\alpha\alpha}\chi$
3. Change $T\alpha\alpha$ to $ATA$. We have derived $A\chi\#(A\chi)^RTA\chi$.

Similarly, we can extend $\chi$ to $B\chi$

The technique, $XY\to YX$

This production rule enables $Y$ to move left when $X$ is to the left of it at the time of derivation.

Although $XY\to YX$ is not a context-sensitive rule, the same generation effect can be realized by the following four context-sensitive rules, where $U$ and $V$ are two new non-terminals.
$\quad XY\to XU$
$\quad XU\to VU$
$\quad VU\to VX$
$\quad VX\to YX$

This technique is used in rule $2$, $3$, $4$, $5$, which enables $\alpha$ and $\beta$ to move left towards $T$, so that they will be changed by rule $6$ and $7$ to $A$ and $B$ respectively.

The real context-sensitive grammar

Here is the solution proper.

$$\begin{aligned} S&\to AS\alpha\alpha \mid BS\beta\beta \mid \#T &\quad & (1)\\ A\alpha&\to A\alpha_A &&(2.1)\\ A\alpha_A&\to\alpha\alpha_A &&(2.2)\\ \alpha\alpha_A&\to A\alpha &&(2.3)\\ B\alpha&\to B\alpha_B &&(3.1)\\ B\alpha_B&\to\alpha\alpha_B &&(3.2)\\ \alpha\alpha_B&\to\alpha B &&(3.3)\\ A\beta&\to A\beta_A &&(4.1)\\ A\beta_A&\to\beta\beta_A &&(4.2)\\ \beta\beta_A&\to\beta A &&(4.3)\\ B\beta&\to B\beta_B &&(5.1)\\ B\beta_B&\to\beta\beta_B &&(5.2)\\ \beta\beta_B&\to\beta B &&(5.3)\\ T\alpha \alpha&\to T\alpha_T\alpha &&(6.1)\\ T\alpha_T\alpha &\to A\alpha_T \alpha &&(6.2)\\ A\alpha_T \alpha&\to A\alpha_TA &&(6.3)\\ A\alpha_T A&\to ATA &&(6.4)\\ T\beta \beta&\to T\beta_T\beta &&(7.1)\\ T\beta_T\beta &\to B\beta_T \beta &&(7.2)\\ B\beta_T \beta&\to B\beta_TB &&(7.3)\\ B\beta_T B&\to BTB &&(7.4)\\ A&\to a&&(8)\\ B&\to b&&(9)\\ T&\to\# &&(10)\\ \end{aligned}$$