المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:نظریه زبان ها و ماشین ها:سوال ۱

سوال ۱

یک ‎NFA‎ طراحی کنید که با خواندن سه عدد ‎$A‎, ‎B‎, ‎C$‎ در مبنای ‎$2$‎ تحقیق کند که آیا تفریق ‎$A$‎ و ‎$B$‎ برابر با ‎$C$‎ است یا نه. رشته ورودی از چپ به راست بصورت زیر داده می شود: ‎$a_1b_1c_1\cdots a_kb_kc_k$. دقت کنید کم‌ارزش‌ترین رقم‌ها اول به ‎NFA‎ وارد می‌شوند. بدیهی است تعداد حالت‌های ‎NFA‎ شما باید مستقل از ‎$K$‎ باشد.


ابزار صفحه