حل تمرین نظریه محاسبات/فصل اول/حل تمرین۱-۴۴

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

حل تمرین 1-44

تمرین[ویرایش]

خانواده‌ای از زبان‌های En را پیدا کنید که En را بتوان با یک NFA با n حالت تشخیص داد ولی برای تشخیص En توسط DFA به یک DFA با حداقل C به توان n حالت نیاز باشد که C یک عدد ثابت و بزرگتر از یک باشد. ثابت کنید که زبان ارائه شده این خاصیت را دارد.

حل[ویرایش]

حل در آدرس زیر است:

http://www.math.ubc.ca/~jf/courses/CS421/hw3sol.pdf

Sipser-1.44.GIF