<p>Your two grammars seem very similar. They are both linear grammars in two non-terminals. (Morally one, really -- in both examples the language of S is contained in the language semiring generated by the language of D.) </p>

<p>It might be worth looking at your example in terms of the <a href="https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_representation_theorem">Chomsky-Schützenberger theorem</a>. The theorem's statement for the two grammars in question is pretty trivial, but you'll probably find that the brace-pair alphabet for the smallest Dyck language of which $L(G_1)$ is a homomorphic image is smaller than the that for $L(G_2)$. (At a glance, I'm counting 3 and 5 respectively.)</p>

CC BY-SA 3.0
2016-06-26T21:47:42.143Z
2016-06-26T21:47:42.143Z
gdmclellan
<p><em>Density</em> might be interesting concept for you. The density function is defined as
$$\delta_L(n) := |L\cap \Sigma^n|,$$</p>

<p>where $\Sigma^n$ denotes the set of all strings of length $n$ over $\Sigma$.</p>

<p>Your first language seems to have density values of only 0 and 1 while the second goes up to 3. So the first is 1-slender, the second is not following the terminology of  <a href="http://www.sciencedirect.com/science/article/pii/S0304397598002667">Lucian Ilie's work</a>.</p>

CC BY-SA 3.0
2016-06-27T15:34:13.940Z
2016-07-17T14:51:04.730Z
2016-07-17T14:51:04.730Z
Peter Leupold
<p>I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known:</p>

<ul>
<li>deterministic/non-deterministic </li>
<li>ambiguous/unambiguous</li>
<li>regular/non-regular</li>
</ul>

<p>As an example of such "non-standard" subclasses are <em>Visibly pushdown grammar</em> described <a href="http://dept-info.labri.fr/~fleury/Formation_Doctorale_2006/papers/AM04.pdf">here</a>. Any additional examples will be much appreciated.</p>

<p><strong>More specifically</strong>, I'm wondering, are any described subclasses which can help distinguish this two very similar cases?</p>

<p>$G_1$:</p>

<p>$S\rightarrow aD$, $S\rightarrow cD$</p>

<p>$D\rightarrow abc$, $D\rightarrow abDc$</p>

<p>$G_2$: </p>

<p>$S\rightarrow aD$, $S\rightarrow cD$</p>

<p>$D\rightarrow abc$, $D\rightarrow abDc$, $D\rightarrow aDb$, $D\rightarrow aDc$</p>

<p>It is clear that both of them are unambiguous non-determ. CFG, and $\mathcal{L}(G_1)\subset\mathcal{L}(G_2)$. But these are common properties, I'm looking for specific differences.</p>

CC BY-SA 3.0
2016-06-26T21:55:00.130Z
Aside: are you sure that $G_1$ is non-deterministic? Why can't a $LR(0)$ parser reduce $abc$ or $abDc$ to $D$ every time it shifts a $c$?
gdmclellan
CC BY-SA 3.0
2016-06-26T23:08:37.857Z
Sorry, why it should (or can) shift *c*? $abDc$ makes this grammar non-regular (produces $(ab)^k abc (c)^k$).
Andrey Lebedev
CC BY-SA 3.0
2016-06-26T23:43:18.947Z
I agree that the language of $D$ isn't regular. However, deterministic languages are a much broader class, encompassing all the $LR$ languages.
gdmclellan
<fl.formal-languages><grammars><context-free>
Known and described subclasses of Context-Free Grammars class
Andrey Lebedev
# Known and described subclasses of Context-Free Grammars class

(Asked by: username_0 on 2016-06-26)

I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known:

* deterministic/non-deterministic
* ambiguous/unambiguous
* regular/non-regular

As an example of such "non-standard" subclasses are *Visibly pushdown grammar* described [here](http://dept-info.labri.fr/~fleury/Formation_Doctorale_2006/papers/AM04.pdf). Any additional examples will be much appreciated.

**More specifically**, I'm wondering, are any described subclasses which can help distinguish this two very similar cases?

$G\_1$:

$S\rightarrow aD$, $S\rightarrow cD$

$D\rightarrow abc$, $D\rightarrow abDc$

$G\_2$:

$S\rightarrow aD$, $S\rightarrow cD$

$D\rightarrow abc$, $D\rightarrow abDc$, $D\rightarrow aDb$, $D\rightarrow aDc$

It is clear that both of them are unambiguous non-determ. CFG, and $\mathcal{L}(G\_1)\subset\mathcal{L}(G\_2)$. But these are common properties, I'm looking for specific differences.

**Tags:** fl.formal-languages, grammars, context-free
> **Comments:**
> **username_1**: Aside: are you sure that $G_1$ is non-deterministic? Why can't a $LR(0)$ parser reduce $abc$ or $abDc$ to $D$ every time it shifts a $c$?  
> **username_0**: Sorry, why it should (or can) shift *c*? $abDc$ makes this grammar non-regular (produces $(ab)^k abc (c)^k$).  
> **username_1**: I agree that the language of $D$ isn't regular. However, deterministic languages are a much broader class, encompassing all the $LR$ languages.  

---

## 2 answers

### Answer by username_2 on 2016-06-27. Score: 10 | Accepted answer

*Density* might be interesting concept for you. The density function is defined as
$$\delta\_L(n) := |L\cap \Sigma^n|,$$

where $\Sigma^n$ denotes the set of all strings of length $n$ over $\Sigma$.

Your first language seems to have density values of only 0 and 1 while the second goes up to 3. So the first is 1-slender, the second is not following the terminology of [Lucian Ilie's work](http://www.sciencedirect.com/science/article/pii/S0304397598002667).


---

### Answer by username_1 on 2016-06-26. Score: 6

Your two grammars seem very similar. They are both linear grammars in two non-terminals. (Morally one, really -- in both examples the language of S is contained in the language semiring generated by the language of D.)

It might be worth looking at your example in terms of the [Chomsky-Schützenberger theorem](https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_representation_theorem). The theorem's statement for the two grammars in question is pretty trivial, but you'll probably find that the brace-pair alphabet for the smallest Dyck language of which $L(G\_1)$ is a homomorphic image is smaller than the that for $L(G\_2)$. (At a glance, I'm counting 3 and 5 respectively.)


---

