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

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

عدد k رامعادل تعداد موقعیت های DFA قرار می دهیم یک DFA باپذیرش تمام جملات با طول K یا بیشتر بانام D میسازیم یک DFA دیگر با نام M با زبانی که برابر اشتراک DFA اولیه و D است را میسازیم اگر EDFA برای M به حالت پذیرش رفت پس DFA اولیه نامتناهی نیست وگرنه هست

4.5.JPG

حل تمرین 4.5 کتاب سیپسر لینک فایل اصلی

http://www.cc.gatech.edu/classes/AY2003/cs3500_summer/sol3.pdf