Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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


ابزار صفحه