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?


1 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$


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.