3 Correction, thanks to https://cs.stackexchange.com/questions/111006 edited Jun 22 at 1:42 Apass.Jack 19.4k22 gold badges1313 silver badges5050 bronze badges 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: We can replace $$XY\rightarrow aX$$ byIt is the following three context-sensitive rules, $$XY\rightarrow NY$$, $$NY\rightarrow NX$$, and $$NX\rightarrow aX$$, where $$N$$ be a new non-terminalsame 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. $$S$$ becomes $$T_1A$$ . $$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. $$A_3A_2$$ is transformed to $$A_2A_3$$ repeatedly so that $$(A_2A_3)^{n}$$ becomes $${A_2}^n{A_3}^n$$. $$T_1A_1$$ is transformed to $$aT_1$$ repeatedly so that $$T_1{A_1}^n$$ becomes $$a^nT_1$$. $$T_1A_2$$ becomes $$bT_2A_2$$. $$T_2A_2$$ is transformed to $$aT_2$$ repeatedly so that $$T_2{A_2}^n$$ becomes $$a^nT_2$$. $$T_2A_3$$ becomes $$bT_3A_3$$. $$T_3A_3$$ is transformed to $$aT_3$$ repeatedly so that $$T_3{A_3}^n$$ becomes $$a^nT_3$$. $$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\}$$. Lemma 1: The non-contracting rule $$XY\rightarrow YX$$ can be rewritten as context-sensitive rules. Proof: 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.  Lemma 2: The non-contracting rule $$XY\rightarrow aX$$ can be rewritten as context-sensitive rules. Proof: We can replace $$XY\rightarrow aX$$ by the following three context-sensitive rules, $$XY\rightarrow NY$$, $$NY\rightarrow NX$$, and $$NX\rightarrow aX$$, where $$N$$ be a new non-terminal. 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. $$S$$ becomes $$T_1A$$ . $$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. $$A_3A_2$$ is transformed to $$A_2A_3$$ repeatedly so that $$(A_2A_3)^{n}$$ becomes $${A_2}^n{A_3}^n$$. $$T_1A_1$$ is transformed to $$aT_1$$ repeatedly so that $$T_1{A_1}^n$$ becomes $$a^nT_1$$. $$T_1A_2$$ becomes $$bT_2A_2$$. $$T_2A_2$$ is transformed to $$aT_2$$ repeatedly so that $$T_2{A_2}^n$$ becomes $$a^nT_2$$. $$T_2A_3$$ becomes $$bT_3A_3$$. $$T_3A_3$$ is transformed to $$aT_3$$ repeatedly so that $$T_3{A_3}^n$$ becomes $$a^nT_3$$. $$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\}$$. 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. $$S$$ becomes $$T_1A$$ . $$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. $$A_3A_2$$ is transformed to $$A_2A_3$$ repeatedly so that $$(A_2A_3)^{n}$$ becomes $${A_2}^n{A_3}^n$$. $$T_1A_1$$ is transformed to $$aT_1$$ repeatedly so that $$T_1{A_1}^n$$ becomes $$a^nT_1$$. $$T_1A_2$$ becomes $$bT_2A_2$$. $$T_2A_2$$ is transformed to $$aT_2$$ repeatedly so that $$T_2{A_2}^n$$ becomes $$a^nT_2$$. $$T_2A_3$$ becomes $$bT_3A_3$$. $$T_3A_3$$ is transformed to $$aT_3$$ repeatedly so that $$T_3{A_3}^n$$ becomes $$a^nT_3$$. $$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\}$$. 2 Simpler explanation. Added two exercise. edited Jun 21 at 22:23 Apass.Jack 19.4k22 gold badges1313 silver badges5050 bronze badges Let us understandLemma 1: The non-contracting rule the grammar for $$a^nb^nc^n$$$$XY\rightarrow YX$$ can be rewritten as context-sensitive rules. First Proof: we can replace $$S$$ is blown$$XY\rightarrow YX$$ by the following three context-up to $$a^nBC(BC)^{n-1}$$. After each CB have been switched to BC successivelysensitive rules, $$BC(BC)^{n-1}$$ becomes $$B^nC^n$$. Replacing each $$B$$ with$$XY\rightarrow NY$$, $$b$$$$NY\rightarrow NX$$, and each $$C$$ with $$c$$$$NX\rightarrow YX$$, we are donewhere $$N$$ be a new non-terminal. Here is how weLemma 2: The non-contracting rule $$XY\rightarrow aX$$ can adaptbe rewritten as context-sensitive rules. Proof: We can replace $$XY\rightarrow aX$$ by the above strategy forfollowing three context-sensitive rules, $$a^nba^nba^nb$$.$$XY\rightarrow NY$$, $$NY\rightarrow NX$$, and $$NX\rightarrow aX$$, where $$N$$ be a new non-terminal. $$S$$ becomes $$Tb$$ so that we will have one $$b$$ at the end. $$T$$ is blown up to $$a^nbXBC(BC)^{n-1}$$. After each CB has been switched to BC successively, $$BC(BC)^{n-1}$$ becomes $$B^nC^n$$. $$XB$$ is switched to $$BX$$ repeatedly so that $$XB^n$$ becomes $$B^nX$$. $$BXC$$ becomes $$BbC$$. Replacing each $$B$$ with $$b$$ and each $$C$$ with $$c$$, we are done. In one lineBecause of the lemma, here iswe will include rules like $$XY\rightarrow YX$$ or $$XY\rightarrow aX$$ in our strategycontext-sensitive grammar with the understanding that each of them represent three context-sensitive rules.$$S\Rightarrow Tb\Rightarrow^*a^nbXBC(BC)^nb\Rightarrow^* a^nbXB^nC^nb\Rightarrow^* a^nbB^nXC^nb\Rightarrow^* a^nbB^nbC^nb\Rightarrow^* a^nba^nba^nb$$ However, there is a big loophole, strings notThe outline of the form $$a^nba^nba^nb$$ might get generated. How can we prevent that from happening? We will require that $$X$$ travelidea to build the right-hand sidegrammar is to meet withlet non-terminal $$E$$, a symbol at$$T_1$$ "travel" from the end of rightleft-hand side that can only be eliminated by its meeting withof $$X$$. We will make sure that$${A_1}^n{A_2}^n{A_3}^n$$ all the only way for $$X$$ to travel to the right-hand side is, transforming each $$A_1$$, $$A_2$$, and $$A_3$$ to go through a bunch of $$B$$'s. Then become$$a$$ along the way as well as updating itself to $$Y$$. Then go through a bunch of$$T_2$$ and then $$C$$'s$$T_3$$ appropriately so as to divide the phases definitively.   Here is the updatedfull strategy in plain words. $$S$$ becomes $$TE$$$$T_1A$$ . $$T$$$$A$$ is blown up to $$a^{n-1}abX(BC)^{n-1}$$$${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. After each CB$$A_3A_2$$ is switchedtransformed to BC successively, $$(BC)^{n-1}$$$$A_2A_3$$ repeatedly so that $$(A_2A_3)^{n}$$ becomes $$B^{n-1}C^{n-1}$$$${A_2}^n{A_3}^n$$. $$XB$$$$T_1A_1$$ is changedtransformed to $$aX$$$$aT_1$$ repeatedly so that $$XB^{n-1}$$$$T_1{A_1}^n$$ becomes $$a^{n-1}X$$$$a^nT_1$$. $$XC$$$$T_1A_2$$ becomes $$abYC$$$$bT_2A_2$$. $$YC$$$$T_2A_2$$ is switchedtransformed to $$aY$$$$aT_2$$ repeatedly so that $$YC^{n-1}$$$$T_2{A_2}^n$$ becomes $$a^{n-1}Y$$$$a^nT_2$$. $$YE$$$$T_2A_3$$ becomes $$ab$$$$bT_3A_3$$. $$T_3A_3$$ is transformed to $$aT_3$$ repeatedly so that $$T_3{A_3}^n$$ becomes $$a^nT_3$$. $$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 partslemma above. In case where $$\Bbb N$$ is understood to change in the next step are underlinedinclude 0, we should add rule $$S\rightarrow bbb$$.\begin{aligned} \underline{S} & \Rightarrow \underline{T}E\\ &\Rightarrow^*a^{n-1}abX\underline{(BC)^{n-1}}E\\ &\Rightarrow^* a^nb\underline{XB^{n-1}}C^{n-1}E\\ & \Rightarrow^* a^nba^{n-1}\underline{XC}C^{n-2}E\\ &\Rightarrow^* a^nba^{n-1}ab\underline{YCC^{n-2}}E\\ & \Rightarrow^* a^nba^{n}ba^{n-1}\underline{YE}\\ &\Rightarrow^* a^nba^{n}ba^{n-1}ab\\ &=a^nba^nba^nb \end{aligned}\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}  There should be enough information to writeExercise 1. Explain why the grammar by nowcannot 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\}$$. Let us understand the grammar for $$a^nb^nc^n$$. First $$S$$ is blown-up to $$a^nBC(BC)^{n-1}$$. After each CB have been switched to BC successively, $$BC(BC)^{n-1}$$ becomes $$B^nC^n$$. Replacing each $$B$$ with $$b$$ and each $$C$$ with $$c$$, we are done. Here is how we can adapt the above strategy for $$a^nba^nba^nb$$. $$S$$ becomes $$Tb$$ so that we will have one $$b$$ at the end. $$T$$ is blown up to $$a^nbXBC(BC)^{n-1}$$. After each CB has been switched to BC successively, $$BC(BC)^{n-1}$$ becomes $$B^nC^n$$. $$XB$$ is switched to $$BX$$ repeatedly so that $$XB^n$$ becomes $$B^nX$$. $$BXC$$ becomes $$BbC$$. Replacing each $$B$$ with $$b$$ and each $$C$$ with $$c$$, we are done. In one line, here is our strategy.$$S\Rightarrow Tb\Rightarrow^*a^nbXBC(BC)^nb\Rightarrow^* a^nbXB^nC^nb\Rightarrow^* a^nbB^nXC^nb\Rightarrow^* a^nbB^nbC^nb\Rightarrow^* a^nba^nba^nb$$ However, there is a big loophole, strings not of the form $$a^nba^nba^nb$$ might get generated. How can we prevent that from happening? We will require that $$X$$ travel to the right-hand side to meet with $$E$$, a symbol at the end of right-hand side that can only be eliminated by its meeting with $$X$$. We will make sure that the only way for $$X$$ to travel to the right-hand side is to go through a bunch of $$B$$'s. Then become $$Y$$. Then go through a bunch of $$C$$'s.   Here is the updated strategy. $$S$$ becomes $$TE$$. $$T$$ is blown up to $$a^{n-1}abX(BC)^{n-1}$$. After each CB is switched to BC successively, $$(BC)^{n-1}$$ becomes $$B^{n-1}C^{n-1}$$. $$XB$$ is changed to $$aX$$ repeatedly so that $$XB^{n-1}$$ becomes $$a^{n-1}X$$. $$XC$$ becomes $$abYC$$. $$YC$$ is switched to $$aY$$ repeatedly so that $$YC^{n-1}$$ becomes $$a^{n-1}Y$$. $$YE$$ becomes $$ab$$. Here is the strategy in terms of formal generation, where the parts to change in the next step are underlined.\begin{aligned} \underline{S} & \Rightarrow \underline{T}E\\ &\Rightarrow^*a^{n-1}abX\underline{(BC)^{n-1}}E\\ &\Rightarrow^* a^nb\underline{XB^{n-1}}C^{n-1}E\\ & \Rightarrow^* a^nba^{n-1}\underline{XC}C^{n-2}E\\ &\Rightarrow^* a^nba^{n-1}ab\underline{YCC^{n-2}}E\\ & \Rightarrow^* a^nba^{n}ba^{n-1}\underline{YE}\\ &\Rightarrow^* a^nba^{n}ba^{n-1}ab\\ &=a^nba^nba^nb \end{aligned} There should be enough information to write the grammar by now. Exercise. Write a grammar for $$\{a^nb^{2n}a^{3n} \mid n \in \Bbb N\}$$. Lemma 1: The non-contracting rule $$XY\rightarrow YX$$ can be rewritten as context-sensitive rules. Proof: 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.Lemma 2: The non-contracting rule $$XY\rightarrow aX$$ can be rewritten as context-sensitive rules. Proof: We can replace $$XY\rightarrow aX$$ by the following three context-sensitive rules, $$XY\rightarrow NY$$, $$NY\rightarrow NX$$, and $$NX\rightarrow aX$$, where $$N$$ be a new non-terminal. 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. $$S$$ becomes $$T_1A$$ . $$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. $$A_3A_2$$ is transformed to $$A_2A_3$$ repeatedly so that $$(A_2A_3)^{n}$$ becomes $${A_2}^n{A_3}^n$$. $$T_1A_1$$ is transformed to $$aT_1$$ repeatedly so that $$T_1{A_1}^n$$ becomes $$a^nT_1$$. $$T_1A_2$$ becomes $$bT_2A_2$$. $$T_2A_2$$ is transformed to $$aT_2$$ repeatedly so that $$T_2{A_2}^n$$ becomes $$a^nT_2$$. $$T_2A_3$$ becomes $$bT_3A_3$$. $$T_3A_3$$ is transformed to $$aT_3$$ repeatedly so that $$T_3{A_3}^n$$ becomes $$a^nT_3$$. $$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\}$$. 1 answered Jun 21 at 7:07 Apass.Jack 19.4k22 gold badges1313 silver badges5050 bronze badges Let us understand the grammar for $$a^nb^nc^n$$. First $$S$$ is blown-up to $$a^nBC(BC)^{n-1}$$. After each CB have been switched to BC successively, $$BC(BC)^{n-1}$$ becomes $$B^nC^n$$. Replacing each $$B$$ with $$b$$ and each $$C$$ with $$c$$, we are done. Here is how we can adapt the above strategy for $$a^nba^nba^nb$$. $$S$$ becomes $$Tb$$ so that we will have one $$b$$ at the end. $$T$$ is blown up to $$a^nbXBC(BC)^{n-1}$$. After each CB has been switched to BC successively, $$BC(BC)^{n-1}$$ becomes $$B^nC^n$$. $$XB$$ is switched to $$BX$$ repeatedly so that $$XB^n$$ becomes $$B^nX$$. $$BXC$$ becomes $$BbC$$. Replacing each $$B$$ with $$b$$ and each $$C$$ with $$c$$, we are done. In one line, here is our strategy. $$S\Rightarrow Tb\Rightarrow^*a^nbXBC(BC)^nb\Rightarrow^* a^nbXB^nC^nb\Rightarrow^* a^nbB^nXC^nb\Rightarrow^* a^nbB^nbC^nb\Rightarrow^* a^nba^nba^nb$$ However, there is a big loophole, strings not of the form $$a^nba^nba^nb$$ might get generated. How can we prevent that from happening? We will require that $$X$$ travel to the right-hand side to meet with $$E$$, a symbol at the end of right-hand side that can only be eliminated by its meeting with $$X$$. We will make sure that the only way for $$X$$ to travel to the right-hand side is to go through a bunch of $$B$$'s. Then become $$Y$$. Then go through a bunch of $$C$$'s. Here is the updated strategy. $$S$$ becomes $$TE$$. $$T$$ is blown up to $$a^{n-1}abX(BC)^{n-1}$$. After each CB is switched to BC successively, $$(BC)^{n-1}$$ becomes $$B^{n-1}C^{n-1}$$. $$XB$$ is changed to $$aX$$ repeatedly so that $$XB^{n-1}$$ becomes $$a^{n-1}X$$. $$XC$$ becomes $$abYC$$. $$YC$$ is switched to $$aY$$ repeatedly so that $$YC^{n-1}$$ becomes $$a^{n-1}Y$$. $$YE$$ becomes $$ab$$. Here is the strategy in terms of formal generation, where the parts to change in the next step are underlined. \begin{aligned} \underline{S} & \Rightarrow \underline{T}E\\ &\Rightarrow^*a^{n-1}abX\underline{(BC)^{n-1}}E\\ &\Rightarrow^* a^nb\underline{XB^{n-1}}C^{n-1}E\\ & \Rightarrow^* a^nba^{n-1}\underline{XC}C^{n-2}E\\ &\Rightarrow^* a^nba^{n-1}ab\underline{YCC^{n-2}}E\\ & \Rightarrow^* a^nba^{n}ba^{n-1}\underline{YE}\\ &\Rightarrow^* a^nba^{n}ba^{n-1}ab\\ &=a^nba^nba^nb \end{aligned} There should be enough information to write the grammar by now. Exercise. Write a grammar for $$\{a^nb^{2n}a^{3n} \mid n \in \Bbb N\}$$.