Well known example of Context-sensitive grammar which produces language $\{a^nb^nc^n|n\geq 1\}$ is widely used in various papers. But actually, while this language is definitely context-sensitive, it is also belongs to smaller subset of CS-languages: it is indexed language, because it can be described with indexed grammar as well.

What I'm looking for, it is example of Context-sensitive grammar which produces non-indexed language. From this paper it is known that language $\{(ab^n)^n|n\geq 1\}$ is not indexed. But there is no described grammar for this language.

So could somebody describe CS-grammar for given non-indexed language example, or provide with any other example?


If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

Example of building word $abbbabbbabbb$ ($n=3$) (added by @Andremoniy):

1) $S\Rightarrow DTA\Rightarrow DDTaA\Rightarrow DDDaaA$ - "inflate" string $n$ times;

2) $\Rightarrow DDabDaA\Rightarrow DabDbDaA\Rightarrow abDbDbDaA\Rightarrow abbDDbDaA\Rightarrow abbbDDDaA\Rightarrow \dots$ - we built 1st subword $abbb$, move on

3) $\Rightarrow abbbDDabDA\Rightarrow abbbDabDbDA\Rightarrow abbbabDbDbDA\Rightarrow abbbabbbDDDA\Rightarrow\dots$ - two subwords $abbbabbb$ are built, move on

4) $\Rightarrow abbbabbbDDAb\Rightarrow abbbabbbDAbb\Rightarrow abbbabbbAbbb\Rightarrow abbbabbbabbb$

| cite | improve this answer | |
  • $\begingroup$ Excuse me, but $Db\rightarrow bD$ is not context-sensitive rule and I don't know how to expand it into sequence of CS-rules. $\endgroup$ – Andrey Lebedev Feb 6 '17 at 21:59
  • $\begingroup$ TBH my grammar in my answer is not proper. I'm working on fixing it though. But I would happy if you could arrange your grammar to canonical view (or at least to Kuroda form). Regards, Andremoniy $\endgroup$ – Andrey Lebedev Feb 6 '17 at 22:50
  • 1
    $\begingroup$ Like I said, it is a noncontracting grammar. There is a standard construction that changes a grammar of this type into a proper context-sensitive grammar. Sorry, but that is boring. $\endgroup$ – Hendrik Jan Feb 6 '17 at 22:54
  • $\begingroup$ OK Thanks. I will try to figure out what more easy to do: transform your or fix my. In any case thank you. $\endgroup$ – Andrey Lebedev Feb 6 '17 at 22:56
  • $\begingroup$ 1) $S\Rightarrow DTA\Rightarrow DDTaA\Rightarrow DDDaaA$ "inflate" string $n$ times $\endgroup$ – Andrey Lebedev Feb 7 '17 at 11:42

First of all I'm very appreciated to @HendrikJan for his example of noncontracting grammar (and his answer which I formally accept). Just to completely end this issue, as I was looking for "canonical" CS grammar ($\alpha A\beta\rightarrow\alpha\gamma\beta$), I'm publishing here my version of transformed @HendrikJan's example to full CS grammar:

$S\rightarrow DTX|ab\\ S\rightarrow DTA|DA$

expanded $DA\rightarrow ABD$:

$DA\rightarrow DY\\ DY\rightarrow WY\\ WY\rightarrow ABY\\ ABY\rightarrow ABD$

expanded $DB\rightarrow BD$:

$DB\rightarrow DU\\ DU\rightarrow IU\\ IU\rightarrow ID\\ ID\rightarrow BD$

expanded $DX\rightarrow Xb$:

$DX\rightarrow DP\\ DP\rightarrow LP\\ LP\rightarrow XP\\ XP\rightarrow Xb$

Finalisations rules:

$X\rightarrow a\\ AB\rightarrow aB\\ aB\rightarrow ab\\ bB\rightarrow bb$

| cite | improve this answer | |

Your Answer

