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.

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

  • $\begingroup$ i will try but i think im to stupid $\endgroup$ – Apfelsaft Jun 21 '19 at 17:38
  • $\begingroup$ I do not know you, but I have been too stupid from time to time. $\endgroup$ – John L. Jun 21 '19 at 22:23
  • $\begingroup$ It should have been "context-sensitive grammar" in exercise 2 and 3. $\endgroup$ – 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


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.