Known and described subclasses of Context-Free Grammars class

Question

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. 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.

Answer 1

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.

Answer 2

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. 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.)