پرش به محتوا

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

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

حل تمرین 29-1

تمرین[ویرایش]

let Bn={Ak|where k is a multiple of n}.show that for each n>=1 the language Bn is regular

حل[ویرایش]

به ازای هر n>=1 ما می‌توانیم یک DFA با n حالت q0,q1,…,qn-1 برای شمارش تعداد a های پشت سر هم n ماژول.برای هر a که ورودیه ما میباشد شمارنده یکی اضافه میشود شدی پرش می کند به حالت بعدی در M.

اگر ما یک نشانه دیگر را انتخاب می کردیم،ما به اشتباه به جایی می رفتیم که هرگز نمی توانستیم بازگردیم. ماشین رشته را قبول می کند به شرطی که به q0 ختم شود و در آنجا تمام شود.این بدین معنی است که طول رشته شامل همه a‌ها می‌باشد که این طول همان مضربی از n است.