3 Correction, thanks to https://cs.stackexchange.com/questions/111006
source | link

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.

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

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.

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

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

2 Simpler explanation. Added two exercise.
source | link

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.

  1. $S$ becomes $Tb$ so that we will have one $b$ at the end.
  2. $T$ is blown up to $a^nbXBC(BC)^{n-1}$.
  3. After each CB has been switched to BC successively, $BC(BC)^{n-1}$ becomes $B^nC^n$.
  4. $XB$ is switched to $BX$ repeatedly so that $XB^n$ becomes $B^nX$.
  5. $BXC$ becomes $BbC$.
  6. 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.

  1. $S$ becomes $TE$$T_1A$ .
  2. $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.
  3. 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$.
  4. $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$.
  5. $XC$$T_1A_2$ becomes $abYC$$bT_2A_2$.
  6. $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$.
  7. $YE$$T_2A_3$ becomes $ab$$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 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$.

  1. $S$ becomes $Tb$ so that we will have one $b$ at the end.
  2. $T$ is blown up to $a^nbXBC(BC)^{n-1}$.
  3. After each CB has been switched to BC successively, $BC(BC)^{n-1}$ becomes $B^nC^n$.
  4. $XB$ is switched to $BX$ repeatedly so that $XB^n$ becomes $B^nX$.
  5. $BXC$ becomes $BbC$.
  6. 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.

  1. $S$ becomes $TE$.
  2. $T$ is blown up to $a^{n-1}abX(BC)^{n-1}$.
  3. After each CB is switched to BC successively, $(BC)^{n-1}$ becomes $B^{n-1}C^{n-1}$.
  4. $XB$ is changed to $aX$ repeatedly so that $XB^{n-1}$ becomes $a^{n-1}X$.
  5. $XC$ becomes $abYC$.
  6. $YC$ is switched to $aY$ repeatedly so that $YC^{n-1}$ becomes $a^{n-1}Y$.
  7. $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.

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

1
source | link

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

  1. $S$ becomes $Tb$ so that we will have one $b$ at the end.
  2. $T$ is blown up to $a^nbXBC(BC)^{n-1}$.
  3. After each CB has been switched to BC successively, $BC(BC)^{n-1}$ becomes $B^nC^n$.
  4. $XB$ is switched to $BX$ repeatedly so that $XB^n$ becomes $B^nX$.
  5. $BXC$ becomes $BbC$.
  6. 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.

  1. $S$ becomes $TE$.
  2. $T$ is blown up to $a^{n-1}abX(BC)^{n-1}$.
  3. After each CB is switched to BC successively, $(BC)^{n-1}$ becomes $B^{n-1}C^{n-1}$.
  4. $XB$ is changed to $aX$ repeatedly so that $XB^{n-1}$ becomes $a^{n-1}X$.
  5. $XC$ becomes $abYC$.
  6. $YC$ is switched to $aY$ repeatedly so that $YC^{n-1}$ becomes $a^{n-1}Y$.
  7. $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\}$.