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

حل تمرین 1-44

تمرین

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

حل

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

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