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

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

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

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