Examples of Context-sensitive grammars which produces non-indexed language

Question

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?

Answer 1

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$

Answer 2

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$