کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426740 686254 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 246, February 2016, Pages 30–42
نویسندگان
, ,