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

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.

• What have you tried? Where did you get stuck? We dislike "do-my-homework" kind of questions around here, so consider adding what were your thoughts about this problem Mar 23 at 18:43
• it's not a homework I have semesterbreak, but I try to solve problems that I weren't able back then. 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. Mar 23 at 19:03
• Some hints on how to build a context-sensitive grammar (or rather, monotonous grammar) and moving symbols around can be seen in: Is there a recommended process for designing CSGs (other than intuition)?. I believe the approach for $\{ww\}$ can be adapted to $\{w\#w^R\#w\}$. Mar 23 at 20:05
• Even if it is not homework, it is of the "do-my-homework" kind, so you should follow @nirshahar's advice to improve your question. Mar 23 at 20:23
• @GR33NTE4 I updated the question with what you said in your comment. What you needed is to show your partial progress or explain the obstacle you encountered in the question. Mar 24 at 7:04

#### 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}

• thanks a lot mate, helped me and my "studygroup" a lot! Mar 26 at 0:25
• @GR33NTE4, you are welcome! Mar 26 at 0:28
• The non-contracting rules are accepted by my uni so that's more than enough. Could you please elaborate on the process how you made these rules? So I get the idea that the α's and 's are some kind of place holders for the actual letters and we split them equally between the middle and the last part, does this "technique" work for all CSG that can be divided into parts? Let's say I had the Language that creates W#W#W#W, would we do sth similar by creating ASααα | BSββββ and then shift them similarly? Thanks in advance! Apr 2 at 6:56
• Yes. It occurs to me that you explain the idea and the technique better than me! Apr 2 at 7:20
• okay, I've used this way for other similar languages and it works just great! I'm finally able to create CSG without doing it planlessly and based on intuition only. Next step understand Decidability lol. Have a good one Apr 2 at 7:49