1
$\begingroup$

When studying Chomsky's hierarchy of languages (starting from type 3), I find enlightening to encounter some language that can't belong to the current type but which very obviously belong to the next level (because some very easy grammar can be described).

For instance, after having studying for a while type-3 (regular grammars), you can easily prove that $\{a^n b^n\}$ or $\{ww^R\}$ are not regular (by using the pumping lemma for the first one, and the pigeonhole principle on the various states of a finite automaton for the second one); but simple type-2 grammars can be described for the very same language.

Now jumping to the type-2 (context-free frammars), you finally encounter $\{a^nb^nc^n\}$ and use a variant of the pumping lemma to show the language can't be context-free; again, a simple context-sensitive grammar can be described.

But I have no good example for the next step; is there some easy proof that such or such language can't be context-sensitive while a rather simple unrestricted grammar (or a Turing Machine for the same language) could be described for it?

I think the following question Is there an example of a recursive language which is not context sensitive? is close to mine, but doesn't focus on the same aspect.

$\endgroup$
3
  • $\begingroup$ Do you consider a universal turing machine implementation to be simple enough to qualify for your intuition? Because it is clear that this language is undecidable and hence type 0: $\{<M>\omega\mid <M> \text{ describes TM }M\text{ and }M\text{ halts on input }\omega\}$ $\endgroup$
    – rici
    Aug 24 at 20:53
  • $\begingroup$ @rici While your answer is perfect, I had something rather different in mind: first, proving the language isn't context-sensitive by relying on some common specific properties of such languages (like my other examples for each respective type); second, showing some "minimal" language from the next type; third, some kind of "concrete" language which could be illustrated by actual examples of words. $\endgroup$ Aug 25 at 8:17
  • $\begingroup$ I had a feeling that would be the case which is why I preflighted that as a comment. It at least clarifies what you are looking for. $\endgroup$
    – rici
    Aug 25 at 14:02
1
$\begingroup$

Since nobody answered my question yet, I have my own try; I would be happy to have comments about it.

Since context-sensitive languages are accepted by linear bounded automata, finding minimalist toy examples of languages which are not context sensitive is not easy, because such automata are already quite powerful.

However, starting from the previous fact, and remembering that:

PSPACE is a strict superset of the set of context-sensitive languages.

(source: https://en.wikipedia.org/wiki/PSPACE)

we can have a look a list of complete PSPACE-problems for finding an idea.

Unfortunately, many PSPACE-complete puzzles are 2D board games (which could be encoded into words of a language, but that wouldn't exactly match the "minimalist" requirement of my initial question), but looking carefully at the list we notice the generalized geography game which can probably be turned into a more or less easy to describe language:

I would be happy to have people simplify my proposal, but here is it.

Let $L$ be a language over three symbols: $a$, $b$ and a separator $","$. Words of this language are split into a list of non-empty substrings made of $a$ and $b$ symbols (splitting obviously occurs at the $","$ symbol locations). We require also the resulting substrings to be of even length. For instance the word aa,baba,bbaa follows the previous requirements. Let's call "country names" such substrings.

Each word in $L$ describes a game, and two players will pick in turn an available country name (no repetition will be allowed). A country name $B$ may follow another one $A$ $iff$ the second half of $A$ matches the first half of $B$. Sizes may differ, for instance $aabb$ may be followed by $bbbaab$ (but not by $abbbbb$ because only the $bb$ part of $aabb$ is taken into account).

A word is in $L$ if the described game is a winning game for the first player. Here is an example of a word in $L$: ab,baba,bb (initial player can pick the second or the third country name and win). Another different example is ab,aa.

I must admit that the "easy to prove" requirement is not fullfilled, but maybe my attempt could give ideas for other answers. Is everything else correct here?

$\endgroup$
1
  • 1
    $\begingroup$ What makes you think this language is not context-sensitive? There are plenty of context-sensitive PSPACE-complete languages, so this fact alone is not helpful. The reason for this is that CSL is not closed under polynomial-time reductions; in fact, the closure of CSL under poly-time reductions is exactly PSPACE. $\endgroup$ Aug 30 at 11:53

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.