1
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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\}$.

$\endgroup$

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.