حل تمرین نظریه محاسبات/فصل اول/حل تمرین۱-۴۴
ظاهر
(تغییرمسیر از حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-44)
حل تمرین 1-44
تمرین
[ویرایش]خانوادهای از زبانهای En را پیدا کنید که En را بتوان با یک NFA با n حالت تشخیص داد ولی برای تشخیص En توسط DFA به یک DFA با حداقل C به توان n حالت نیاز باشد که C یک عدد ثابت و بزرگتر از یک باشد. ثابت کنید که زبان ارائه شده این خاصیت را دارد.
حل
[ویرایش]حل در آدرس زیر است: