snippetMinor
How to give a context-sensitive grammar for a^nba^nba^nb?
Viewed 0 times
givegrammarfornbahowcontextsensitive
Problem
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.
Solution
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.
\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.
Context
StackExchange Computer Science Q#110985, answer score: 4
Revisions (0)
No revisions yet.