حل تمرین نظریه محاسبات/فصل اول/حل تمرین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 است.