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?


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

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


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

  • 1
    $\begingroup$ 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$? $\endgroup$ – gdmclellan Jun 26 '16 at 21:55
  • $\begingroup$ Sorry, why it should (or can) shift c? $abDc$ makes this grammar non-regular (produces $(ab)^k abc (c)^k$). $\endgroup$ – Andrey Lebedev Jun 26 '16 at 23:08
  • $\begingroup$ I agree that the language of $D$ isn't regular. However, deterministic languages are a much broader class, encompassing all the $LR$ languages. $\endgroup$ – gdmclellan Jun 26 '16 at 23:43

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.