3
$\begingroup$

This question can look like some kind of puzzle, but it is actually part of more complex applied problem.

Let's consider subspace of Context-Sensitive Grammars, which contains grammars which can not be represented neither as Context-Free Grammars, neither as Regular Grammars. Let's call them "strong CSG".

And let's suppose that we are given only by alphabet, set of nonterminals, set of production rules, but without left sides (which is hidden from us). For instance:

$\Sigma=\{a,b,c\}$ $N=\{S,B,W,X\}$

and rules:

  1. $?\rightarrow abc$
  2. $?\rightarrow aSBc$
  3. $?\rightarrow WB$
  4. $?\rightarrow WX$
  5. $?\rightarrow BX$
  6. $?\rightarrow Bc$
  7. $?\rightarrow bb$

The question is: are any general properties regarding right-side of these production rules using which we can distinguish strong-CSG from CFG and RG looking only on this non-complete set of rules?

Alternative formulation of this question: in this particular case, can given grammar be Context-free?

Let's also consider that in case of CFG given grammar is always present in reduced (simplified) form (by reduction I mean finding a CFG with the fewest nonterminal symbols or with the fewest rules that is equivalent to G) - (we're talking here about weak-equivalent grammar with smallest number of non-terminals and production rules - thanks to @Marzio De Biasi for pointing this).

Disclaimer: original grammar was Context-Sensitive, taken from wikipedia article.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Can you give a formal definition of "reduced (simplified) form" for a Context Sensitive Grammar (or a reference)? I made a quick search but didn't find an exact definition and the only "normal form" I remember for CSGs is Kuroda normal form. $\endgroup$ – Marzio De Biasi Oct 20 '16 at 7:32
  • $\begingroup$ @MarzioDeBiasi Thank you, that's good point. It actually was confusing statement. I meant that in case when given grammar is CF, then it is in reduced form. I've updated my question to make it more clear. $\endgroup$ – Andrey Lebedev Oct 20 '16 at 8:26
  • 1
    $\begingroup$ @MarzioDeBiasi by reduction I mean finding a CFG with the fewest nonterminal symbols or with the fewest rules that is equivalent to G, see for instance sciencedirect.com/science/article/pii/S0019995870800079 $\endgroup$ – Andrey Lebedev Oct 20 '16 at 9:06
  • 2
    $\begingroup$ Ok, thanks; I gave a quick look at the paper and there are two notions: "weakly equivalent" and "structural equivalence"; the first seems undecidable; so your problem can potentially be undecidable; indeed if the left side can be "filled" to get a valid CFG $G$ (e.g. for your example X->abc, S->aSBc, S->WB, W->WX, W->BX, B->Bc, B->bb), then we should check that there is not a smaller (reduced) grammar $G'$ which is weakly equivalent to $G$ (if there is one, then $G$ violates the "promise"); but this is undecidable. $\endgroup$ – Marzio De Biasi Oct 20 '16 at 9:45
  • 1
    $\begingroup$ @MarzioDeBiasi thanks for your exploration, this could be an accepted answer, as you provided good conterexample. $\endgroup$ – Andrey Lebedev Oct 20 '16 at 9:59

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.