المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۷:ترکیبیات:سوال ۵

ایلیچ‌کانورت و سلطان‌کانورت

فرض کنید $s$ یک رشته باشد. هرگاه تعدادی از حروف $s$ را انتخاب کنیم، طوری که هیچ دو حرف انتخاب شده در رشته مجاور نباشند، یک امبیشیوس از $s$ ساخته‌ایم. ایلیچ‌کانورت $s$ که با $IC(s)$ نشان داده می‌شود، مجموعه‌ی تمام امبیشیوس‌های $s$ است. برای مثال: $$IC(abaac) = \{\epsilon, a, b, c, aa, ac, ba, bc, aac\}$$ فرض کنید $L$ یک زبان باشد. سلطان‌کانورت $L$ را که با $SC(L)$ نشان داده می‌شود، به صورت زیر تعریف می‌کنیم: $$SC(L) = \bigcup_{s \in L} IC(s)$$ ثابت کنید اگر $L$ زبانی منظم باشد، $SC(L)$ نیز منظم است.


ابزار صفحه