کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952062 1442009 2017 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Languages with membership determined by single letter factors
ترجمه فارسی عنوان
زبان با عضویت توسط یک حرف مشخص تعیین می شود
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The full scan condition on a language L introduced in [1] ensures that a word w must be completely inspected in order to decide whether or not w lies in L. We strengthen the condition by replacing the factor words in that definition by single letters. After examining the general case for both arbitrary and regular languages, we investigate the two-letter alphabet to find a complete description of the corresponding languages, which may be coded as infinite binary strings. Regularity of these languages corresponds to the associated numbers being rational and we find the minimal automata in all cases, which may be pictured as a cylinder of tape with a protruding end, although this cylinder is replaced by a Möbius strip for a special class of rational languages.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 680, 5 June 2017, Pages 15-24
نویسندگان
, ,