On bounded languages and reversal-bounded automata

Bounded context-free languages have been investigated for nearly fifty years, yet they continue to generate interest as seen from recent studies. Here, we present a number of results about bounded context-free languages. First we give a new (simpler) proof that every context-free language L⊆w1⁎w2⁎…wn⁎ can be accepted by a PDA with at most 2n−32n−3 reversals. We also introduce new collections of bounded context-free languages and present some of their interesting properties. Some of the properties are counter-intuitive and may point to some deeper facts about bounded CFLs. We present some results about semilinear sets and also present a generalization of the well-known result that over a one-letter alphabet, the families of context-free and regular languages coincide.