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

<p>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 "<em>strong</em> CSG". </p>

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

<p>$\Sigma=\{a,b,c\}$
$N=\{S,B,W,X\}$</p>

<p>and rules:</p>

<ol>
<li>$?\rightarrow abc$</li>
<li>$?\rightarrow aSBc$</li>
<li>$?\rightarrow WB$</li>
<li>$?\rightarrow WX$</li>
<li>$?\rightarrow BX$</li>
<li>$?\rightarrow Bc$</li>
<li>$?\rightarrow bb$</li>
</ol>

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

<p><strong><em>Alternative formulation of this question</em></strong>: in this particular case, can given grammar be Context-free? </p>

<p>Let's also consider that in case of CFG given grammar is always present in <a href="http://www.sciencedirect.com/science/article/pii/S0019995870800079" rel="nofollow">reduced</a> (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).</p>

<p><em>Disclaimer</em>: original grammar was Context-Sensitive, taken from wikipedia article.</p>

CC BY-SA 3.0
2016-10-20T07:32:45.977Z
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.
Marzio De Biasi
CC BY-SA 3.0
2016-10-20T08:26:12.243Z
@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.
Andrey Lebedev
CC BY-SA 3.0
2016-10-20T08:45:20.157Z
But even for CFGs  "*reduced (simplified) form*" seems not a standard/frequently-used term (but I'm not an expert) and you should clarify what it means. Do you mean "Chomsky normal form" (or equivalently "Chomsky reduced form")? Obviously, in that case, the ?->aSBc, ?->abc, ?->Bc, ?->bb rules imply that the given grammar is not CF (assuming that if it is CF then it is given in Chomsky normal form)
Marzio De Biasi
CC BY-SA 3.0
2016-10-20T09:06:40.260Z
@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 http://www.sciencedirect.com/science/article/pii/S0019995870800079
Andrey Lebedev
CC BY-SA 3.0
2016-10-20T09:45:40.770Z
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.
Marzio De Biasi
CC BY-SA 3.0
2016-10-20T09:59:35.390Z
@MarzioDeBiasi thanks for your exploration, this could be an accepted answer, as you provided good conterexample.
Andrey Lebedev
CC BY-SA 3.0
2016-10-20T13:20:20.127Z
@MarzioDeBiasi Please look at my commentary under your answer.
Andrey Lebedev
CC BY-SA 3.0
2016-10-20T15:04:26.947Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/47127/discussion-between-marzio-de-biasi-and-andremoniy).
Marzio De Biasi
<fl.formal-languages><grammars><context-free>
Context-Sensitive Grammar characteristic properties
Andrey Lebedev
# Context-Sensitive Grammar characteristic properties

(Asked by: username_0 on 2016-10-19)

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](http://www.sciencedirect.com/science/article/pii/S0019995870800079) (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 @username_1 for pointing this).

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

**Tags:** fl.formal-languages, grammars, context-free

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: But even for CFGs  "*reduced (simplified) form*" seems not a standard/frequently-used term (but I'm not an expert) and you should clarify what it means. Do you mean "Chomsky normal form" (or equivalently "Chomsky reduced form")? Obviously, in that case, the ?->aSBc, ?->abc, ?->Bc, ?->bb rules imply that the given grammar is not CF (assuming that if it is CF then it is given in Chomsky normal form)  
> **username_0**: @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 http://www.sciencedirect.com/science/article/pii/S0019995870800079  
> **username_1**: 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.  
> **username_0**: @MarzioDeBiasi thanks for your exploration, this could be an accepted answer, as you provided good conterexample.  
> **username_0**: @MarzioDeBiasi Please look at my commentary under your answer.  
> **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/47127/discussion-between-marzio-de-biasi-and-andremoniy).  

---

## 0 answers

