1
$\begingroup$

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?

$\endgroup$

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.