Advertisement
Published in:
2013 | OriginalPaper | Chapter
On Bounded Languages and Reversal-Bounded Automata
Authors : Oscar H. Ibarra, Bala Ravikumar
Published in: Language and Automata Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 \subseteq w_1^* w_2^* ... w_n^*$
can be accepted by a PDA with at most 2
n
− 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 CFL’s. We present some results about semilinear sets and also present a generalization of the well-known result that over a one-letter alphabet, the family of context-free and regular languages coincide.