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

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.

• What kind of grammar are you looking for? – Yuval Filmus Jun 20 '19 at 17:53
• Typ1 grammar context-sensitive – Apfelsaft Jun 20 '19 at 19:38
• Try adapting a grammar for $\{ a^n b^n c^n \mid n \in \mathbb{N} \}$. Wikipedia gives such a grammar. – Yuval Filmus Jun 20 '19 at 19:40
• i did. but find nothing... – Apfelsaft Jun 20 '19 at 19:41
• Perhaps you should try harder. – Yuval Filmus Jun 20 '19 at 19:42

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.

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\}$$.

• i will try but i think im to stupid – Apfelsaft Jun 21 '19 at 17:38
• I do not know you, but I have been too stupid from time to time. – John L. Jun 21 '19 at 22:23
• It should have been "context-sensitive grammar" in exercise 2 and 3. – John L. Jun 22 '19 at 22:29

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