Is { a^nb^na^n} a context-sensitive language?

Question

The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language.

I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?

Answer 1

The grammar:

$S\to aS'Ba\mid aba \mid\varepsilon$

$S'\to aS'Ba\mid aba$ (so that only the start symbol can generate the empty word)

$aB \to Ba$ (to move the inner $a$'s to the right)

$bB \to bb$ (to transform all $B$'s into $b$'s)

is a noncontracting grammar generating the language $\{a^nb^na^n\mid n\geqslant 0\}$. That means the language is context-sensitive.

Beware that the previous grammar is not context-sensitive (the problematic rule is $aB\to Ba$).

If you want a context-sensitive grammar, it is a bit more complicated. Something like this should work:

$S\to aS'BA\mid aba \mid \varepsilon$

$S' \to aS'BA\mid abA$

$AB\to XB$

$XB \to XY$

$XY\to BY$

$BY \to BA$

$bB\to bb$

$A \to a$