<p>Every context free language over a one letter alphabet (or equivalently every langauge recognized by unary PDAs, unary DPDAs or 1 counter machines) is <em>regular</em>.</p>

<p>See: <a href="http://dl.acm.org/citation.cfm?doid=321127.321132" rel="nofollow">S. Ginsburg, H. Rice: "Two families of languages related to ALGOL", Journal of the
ACM, 9: 350–371, 1962</a>.</p>

<p>For what regards PDAs with bounded stack reversals they are equivalent to <em>bounded context-free languages</em>. In general a language $L$ over alphabet $\Sigma$ (with $|\Sigma|\geq 2$) is <em>bounded</em> 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 <em>finite union of stratified linear sets</em> see Ginsburg's theorem). <br>I don't know much about them, but they have been studied intensively, see for example: <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-37064-9_32" rel="nofollow">Oscar H. Ibarra, Bala Ravikumar , On Bounded Languages and Reversal-Bounded Automata</a> (citing and cited articles).</p>

<p>EDIT: another result is that <em>linear LR(1) languages</em> are equivalent to the class of languages accepted by deterministic <em>one-turn</em> PDA (M. Holzer, K. J. Lange, On the Complexities of Linear LL(1) and LR(1) Grammars)</p>

CC BY-SA 3.0
2014-07-05T05:44:00.010Z
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!
Joey Eremondi
CC BY-SA 3.0
2014-07-05T11:53:26.560Z
@jmite, ok! For what regards one-counter DFAs I know some hierarchy stuff (see my [answer on cs.stackexchange](http://cs.stackexchange.com/a/7575/140) ), but I'm not aware of *grammar characterizations* of them (but I'm not an expert)  ... I look forward to other answers along this direction.
Marzio De Biasi
CC BY-SA 3.0
2014-07-04T22:14:48.797Z
2014-07-05T12:03:07.430Z
2014-07-05T12:03:07.430Z
Marzio De Biasi
<p>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)$.</p>

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

<p>In particular, I'm interested in:</p>

<ul>
<li>Pushdown Automata with a bound on the number of reversals the stack can make.</li>
<li>Pushdown Automata with a unary stack alphabet (i.e. counter machines)</li>
</ul>

CC BY-SA 3.0
2014-07-05T16:32:44.070Z
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.
Vijay D
<reference-request><fl.formal-languages><automata-theory><grammars><context-free>
What characterizations exist for the grammars that can express subsets of the context-free languages?
Joey Eremondi
# What characterizations exist for the grammars that can express subsets of the context-free languages?

(Asked by: username_0 on 2014-07-04)

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)

**Tags:** reference-request, fl.formal-languages, automata-theory, grammars, context-free

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-07-04. Score: 5

Every context free language over a one letter alphabet (or equivalently every langauge recognized by unary PDAs, unary DPDAs or 1 counter machines) is *regular*.

See: [S. Ginsburg, H. Rice: "Two families of languages related to ALGOL", Journal of the
ACM, 9: 350–371, 1962](http://dl.acm.org/citation.cfm?doid=321127.321132).

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 don't know much about them, but they have been studied intensively, see for example: [Oscar H. Ibarra, Bala Ravikumar , On Bounded Languages and Reversal-Bounded Automata](http://link.springer.com/chapter/10.1007%2F978-3-642-37064-9_32) (citing and cited articles).

EDIT: another result is that *linear LR(1) languages* are equivalent to the class of languages accepted by deterministic *one-turn* PDA (M. Holzer, K. J. Lange, On the Complexities of Linear LL(1) and LR(1) Grammars)

> **Comments:**
> **username_0**: 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!  
> **username_2**: @jmite, ok! For what regards one-counter DFAs I know some hierarchy stuff (see my [answer on cs.stackexchange](http://cs.stackexchange.com/a/7575/140) ), but I'm not aware of *grammar characterizations* of them (but I'm not an expert)  ... I look forward to other answers along this direction.  

---

