کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426740 | 686254 | 2016 | 13 صفحه PDF | دانلود رایگان |
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.
Journal: Information and Computation - Volume 246, February 2016, Pages 30–42