How to give a context-sensitive grammar for a^nba^nba^nb?

Question

I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.

Answer 1

One possible grammar is:

\begin{align} S&\rightarrow Tb &(1)\\ T&\rightarrow AXY &(2)\\ T&\rightarrow ATXY &(3)\\ YX&\rightarrow YZ &(4)\\ YZ&\rightarrow WZ &(5)\\ WZ&\rightarrow WY &(6)\\ WY &\rightarrow XY &(7)\\ AX &\rightarrow AbA_X &(8)\\ A_XX&\rightarrow A_XA_X &(9)\\ A_XY&\rightarrow A_XbA_Y &(10)\\ A_YY&\rightarrow A_YA_Y &(11)\\ A&\rightarrow a &(12)\\ A_X&\rightarrow a &(13)\\ A_Y&\rightarrow a &(14) \end{align}

We can generate $A^n(XY)^n$ using Rule (1) to (3). Rule (4) to (7) are used to change $YX$ to $XY$, thus we can generate $A^nX^nY^n$. At last, using Rule (8) to (14) we can generate $a^nba^nba^nb$.

Note we needn't worry that in a pattern $YX$, $Y$ yields to $A_Y$ (or $bA_Y$) before we exchange $X$ and $Y$, because otherwise there is no rule to eliminate $X$ in this pattern.

Answer 2

Lemma 1: The non-contracting rule $XY\rightarrow YX$ can be rewritten as context-sensitive rules.
Proof: If that rule is the only rule in the grammar where $Y$ appears on its left-hand side, we can replace $XY\rightarrow YX$ by the following three context-sensitive rules, $XY\rightarrow NY$, $NY\rightarrow NX$, and $NX\rightarrow YX$, where $N$ be a new non-terminal.
We will not use the case when $Y$ also appears on the left-hand side of other rules.

Lemma 2: The non-contracting rule $XY\rightarrow aX$ can be rewritten as context-sensitive rules.
Proof: It is the same as the above.

Because of the lemma, we will include rules like $XY\rightarrow YX$ or $XY\rightarrow aX$ in our context-sensitive grammar with the understanding that each of them represent three context-sensitive rules.

---

The outline of the idea to build the grammar is to let non-terminal $T_1$ "travel" from the left-hand side of ${A_1}^n{A_2}^n{A_3}^n$ all the way to the right-hand side, transforming each $A_1$, $A_2$, and $A_3$ to $a$ along the way as well as updating itself to $T_2$ and then $T_3$ appropriately so as to divide the phases definitively.

Here is the full strategy in plain words.

1. $S$ becomes $T_1A$ .
2. $A$ is blown up to ${A_1}^n(A_2A_3)^n$ by rules $A\rightarrow A_1A(A_2A_3)\mid A_1(A_2A_3)$. Note "(" anf ")" are used to indicate operating precedence. They are not terminals nor non-terminals.
3. $A_3A_2$ is transformed to $A_2A_3$ repeatedly so that $(A_2A_3)^{n}$ becomes ${A_2}^n{A_3}^n$.
4. $T_1A_1$ is transformed to $aT_1$ repeatedly so that $T_1{A_1}^n$ becomes $a^nT_1$.
5. $T_1A_2$ becomes $bT_2A_2$.
6. $T_2A_2$ is transformed to $aT_2$ repeatedly so that $T_2{A_2}^n$ becomes $a^nT_2$.
7. $T_2A_3$ becomes $bT_3A_3$.
8. $T_3A_3$ is transformed to $aT_3$ repeatedly so that $T_3{A_3}^n$ becomes $a^nT_3$.
9. $T_3$ is changed to b.

Here is the full strategy in terms of formal generation.

$$\begin{aligned} S &\Rightarrow T_1A\\ &\Rightarrow^* T_1A_1^n(A_2A_3)^n\\ &\Rightarrow^*T_1{A_1}^n{A_2}^n{A_3}^n\\ &\Rightarrow^*a^nT_1{A_2}^n{A_3}^n\\ &\Rightarrow^*a^nbT_2{A_2}^n{A_3}^n\\ &\Rightarrow^*a^nba^nT_2{A_3}^n\\ &\Rightarrow^*a^nba^nbT_3{A_3}^n\\ &\Rightarrow^*a^nba^nba^nT_3\\ &\Rightarrow a^nba^nba^nb \end{aligned}$$

Here is the context-sensitive grammar, where each of rule (3), rule (4), rule (6), and rule (8) stands for three context sensitive rules as given by the lemma above. In case where $\Bbb N$ is understood to include 0, we should add rule $S\rightarrow bbb$.

\begin{align} S&\rightarrow T_1A &(1)\\ A&\rightarrow A_1AA_2A_3 \mid A_1A_2A_3 &(2)\\ A_3A_2&\rightarrow A_2A_3 &(3)\\ T_1A_1&\rightarrow aT_1 &(4)\\ T_1A_2&\rightarrow bT_2A_2 &(5)\\ T_2A_2 &\rightarrow aT_2 &(6)\\ T_2A_3 &\rightarrow aT_3A_3 &(7)\\ T_3A_3 &\rightarrow aT_3 &(8)\\ T_3&\rightarrow b &(9)\\ \end{align}

---

Exercise 1. Explain why the grammar cannot generate any string that is not of the form $a^nba^na^nb$.

Exercise 2. Write a grammar for $\{a^nb^{2n}a^{3n} \mid n \in \Bbb N\}$.

Exercise 3. Write a grammar for $\{a^{n+n^2} \mid n \in \Bbb N\}$.

Answer 3

I like the feature sensitive grammar notaion, means for each term is a set of features assigned, what must be matched inside a rule. The rule will be just:

S[a_count = n]-> a{n}b a{n}b a{n}b ,

Compare it to notations above with 10 rules. While matching the feature rule, parser will mach amount of a's and assign the value to S.a_count field. Dont forget, a parser is a turing complete program in praxis.

Further, arithmetical expression are possible :

S[a_count = n]-> a{n}b{2*n}c{3*n},

Exercise 3 is not possible with this notation, it is something like :

S[a_count = m]-> a{m} : m == n + n*n , n in N

so equasion must be solved here