Language of equal numbers of as, bs, cs in any order not context-sensitive?

In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $$L = \{ w \in \{a,b,c\}^*\ |\ |w|_a=|w|_b=|w|_c \}$$, where $$|w|_a$$ denotes the number of $$a$$s in a word $$w$$. This language is a variant of the language $$L_1 = \{ a^nb^nc^n |\ n>0 \}$$ which is context-sensitive.

Later, he says that this language is not context-sensitive because "the working strings grow beyond a constant times the size of the initial input before shrinking down to the final output."

However, I can think of a Turing machine that first sorts the input (in a linear space n + c, where n is the input size and c is a constant such as 1) and then accepts/rejects in the very same manner as the machine accepting the language $$L_1$$. Both subroutines are also linear bounded and thus the machine itself is a linear bounded automaton (LBA). Context-sensitive languages are accepted by LBAs, therefore the language $$L$$ is context-sensitive.

Where am I mistaken?

• What's $c$ in your $n+c$? Aug 21 at 0:10
• It's a constant, potentially needed for the "working" tape, c=1 or c=2 for some sorting algorithms Aug 21 at 5:02

1 Answer

It seems the author of the book is a little careless at this point. His definition of context-sensitive is that "the right-hand side of a rule must never be shorter than the left-hand side" together with a specific assumption that enables us to generate the empty string.

He states "The grammars in Examples 9–1 and 9–2 are not context-sensitive. In both cases, the working strings grow beyond a constant times the size of the initial input before shrinking down to the final output."

This is confusing. In his Example 9-1 for equal numbers of $$a$$, $$b$$ and $$c$$'s the only contracting rule is $$S\to \lambda$$ which can be easily transformed into a grammar where $$S$$ does not appear to the right of a rule by introducing a new copy of $$S$$. Then you will have a proper non-contracting grammar for the language you are interested in.

The other Example 9-2 for $$\{ a^{2^n}\mid n\ge 0\}$$ has several rules that are contracting, like $$GR\to R$$ and $$XA\to X$$. In this case there seems no fast solution, but with proper care also here one can design a noncontracting grammar for the language.

Then, I quote, "The languages generated by those grammars are not context-sensitive". This is not true as you suspected. Both languages can be recognized by a linear space Turing machine, or generated by noncontracting grammar.

(I prefer noncontracting here, as context-sensitive is usually a more restrictive type of grammar, which nevertheless is equally powerful.)

PS. For the second example several solutions can be found at Context sensitive grammar for $$\{a^{2^n}\mid n\ge 0\}$$.