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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.