# What characterizations exist for the grammars that can express subsets of the context-free languages?

It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$.

I'm wondering, what results are known about classes of grammars that can generate the languages accepted by other restricted versions of pushdown automata?

In particular, I'm interested in:

• Pushdown Automata with a bound on the number of reversals the stack can make.
• Pushdown Automata with a unary stack alphabet (i.e. counter machines)
• You may also be interested in Visibly Pushdown Languages, which have also been characterized as languages of nested words. The stack operation is defined by the input symbol. These languages are a subset of CFLs but have closure properties like regular languages. Jul 5, 2014 at 16:32

For what regards PDAs with bounded stack reversals they are equivalent to bounded context-free languages. In general a language $L$ over alphabet $\Sigma$ (with $|\Sigma|\geq 2$) is bounded if and only if there exists non empty words $w_1,w_2,...,w_n$ such that $L\ \subseteq w_1^*w_2^*...w_n^*$; but not all bounded languages are context-free (for a characterization of bounded CFG languages by finite union of stratified linear sets see Ginsburg's theorem).
• I wasn't talking about unary input alphabet, but unary stack alphabet i.e. you can add or subtract, but not store different symbols. These are more powerful than DFAs, for example they can accept $\{a^n b^n \mid n \geq 0 \}$ Still interesting though, especially the bounded results! Jul 5, 2014 at 5:44