حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۳۸

ویکی‎کتاب، کتابخانهٔ آزاد

1.38 all NFA یک مجموعه ی 5تایی ,q0 ,F)δ ∑ (Q,است که زمانی رشته ی x را می پذیرد که همه ی حالت های ممکن بعد از خواندن x جز حالت های پذیرش باشد. بر عکس NFA که کافی است بعد از خواندن x حداقل یکی از آنها حالت پذیرش باشد.ثابت کنید all NFA ها زبان های منظم را تشخیص می دهند.