2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\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
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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