4
$\begingroup$

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)
Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Vijay D
    Commented Jul 5, 2014 at 16:32

1 Answer 1

Reset to default
5
$\begingroup$

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.

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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! $\endgroup$
    – Joey Eremondi
    Commented Jul 5, 2014 at 5:44
  • $\begingroup$ @jmite, ok! For what regards one-counter DFAs I know some hierarchy stuff (see my answer on cs.stackexchange ), 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. $\endgroup$
    – Marzio De Biasi
    Commented Jul 5, 2014 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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