2
$\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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Very closely related question; duplicate? $\endgroup$
    – Raphael
    Commented Oct 11, 2017 at 10:36
  • $\begingroup$ The PCP may be worth a look. $\endgroup$
    – Raphael
    Commented Oct 11, 2017 at 10:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.