To present interesting type-0 grammars to my students, I am looking for a very simple example of a type-0 language (=recursively enumerable language) that is not of type-1 (=not context sensitive). I am hoping for a language that is generated by a very small grammar, like two or three very short production rules or something like that.
The most simple examples I could think of so far:
- The halting problem, or similar semi-decidable problems.
- Any ExpSpace-complete problem, since these are not decidable in nondeterministic linear Space, which equals type-1 languages.
- There are very small universal Turing Machines, but translating these into grammars gives a blow up again.
So for neither of these problems I see a simple way to encode them in a very short grammar or very small grammar.
Do you have any idea how to find such an example?