0
$\begingroup$

If given a grammar, for example, a context-sensitive (type 1) can it always be "reduced" to a equivalent context-free grammar (type 2) and so on for grammars type 2 to "reducing" and getting a type 3?

How can I prove or show that this is undecidable? (if this is the case)

I know that is undecidable whether a context-free grammar has a equivalent regular grammar. And so on for a sensitive-context having a equivalent context-free grammar, but don't know how to generalize it.

P.s.: When I say "reducing" I mean the lower level in Chomsky Hierarchy, considering type 0 the top and the lowest is the type 3.

$\endgroup$
9
  • 1
    $\begingroup$ No, it isn't. There may or may not be a "reduced" grammar for the same language. If there isn't one, obviously no Turing machine can invent one. Wirse, it is not decidable whether an equivalent grammar exists. $\endgroup$
    – rici
    Jul 7, 2018 at 23:26
  • $\begingroup$ For the other grammars, I mean, given a context-sesitive can I always get a equivalent context-free and so on for the other grammars? Where do I read about this undecidable problem? Thanks a lot! $\endgroup$
    – archtes
    Jul 8, 2018 at 15:38
  • $\begingroup$ No, you can't. Context-sensitive grammars produce a strictly larger set of languages. The undecidability proof is in Chomsky's original paper iirc, and it is certainly in Introduction to Automata Theory, Languages and Computation, by Hopcroft & Ullman. $\endgroup$
    – rici
    Jul 8, 2018 at 19:23
  • 1
    $\begingroup$ A very similar question was recently asked and then deleted by Léo Eduardo Silva (cs.stackexchange.com/questions/94030/…). Are you the same person, or just taking the same class? $\endgroup$ Jul 9, 2018 at 17:13
  • $\begingroup$ I don't know what was this question, can't see it: page not found. I don't know what his question is about. Did he get any answer? I'm curious. $\endgroup$
    – archtes
    Jul 9, 2018 at 17:29

0