3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ What kind of grammar are you looking for? $\endgroup$ Commented Jun 20, 2019 at 17:53
  • $\begingroup$ Typ1 grammar context-sensitive $\endgroup$
    – Apfelsaft
    Commented Jun 20, 2019 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$ Commented Jun 20, 2019 at 19:40
  • $\begingroup$ i did. but find nothing... $\endgroup$
    – Apfelsaft
    Commented Jun 20, 2019 at 19:41
  • $\begingroup$ Perhaps you should try harder. $\endgroup$ Commented Jun 20, 2019 at 19:42

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Lemma 1: The non-contracting rule $XY\rightarrow YX$ can be rewritten as context-sensitive rules.
Proof: We can replace $XY\rightarrow YX$ with the following four context-sensitive rules,
$\quad XY\rightarrow UY$,
$\quad UY\rightarrow UV$,
$\quad UV\rightarrow UX$,
$\quad UX\rightarrow YX$,
where $U, V$ are new non-terminals.

Lemma 2: The non-contracting rule $XY\rightarrow aX$ can be rewritten as context-sensitive rules.
Proof: Similarly to lemma 1, we can replace $XY\rightarrow aX$ with the following four rules,
$\quad XY\rightarrow UY$,
$\quad UY\rightarrow UV$,
$\quad UV\rightarrow aV$,
$\quad aV\rightarrow aX$,
where $U, V$ are new non-terminals.

Because of the lemmas, we will include rules like $XY\rightarrow YX$ or $XY\rightarrow aX$ in our context-sensitive grammar with the understanding that each of them represents four 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$ to indicate different phases.

Here is the strategy.

  1. $S$ becomes $T_1A$ .
  2. $A$ is blown up to ${A_1}^n(A_2A_3)^n$ by rules $A\rightarrow A_1AA_2A_3\mid A_1A_2A_3$.
  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 strategy in terms of formal derivation.

$$\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 four context sensitive rules as given by the lemmas above. In the case when $0\in\Bbb N$, 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 strings generated by the grammar above must be 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\}$.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.