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

سوال)

    نشان دهید زبان  { w یک عدد باینری است که مضربی از n باشد| Cn = {w   به ازای n ≥ 1 منظم است.

پاسخ)

    برای نشان دادن منظم بودن یک زبان کافیست یک DFA پیدا کنیم که آن زبان را بپذیرد.این DFA را می توان به صورت زیر ساخت :

N = ( Q, ∑, ∂, q, F)

 Q = { S0, S1, …, Sn – 1 } 

که در state های مشخص شده Si به معنای حالتی است که تا کنون باقیمانده برابر i است.

∑ = {0, 1}

q = S0

F = { S0 }

∂ ( Si , 0 ) = S (2 * i ) % n , ∂ ( Si , 1 ) = S ( 2 * i + 1) % n

به این ترتیب یک DFA برای پذیرفتن این زبان بدست آوردیم پس این زبان منظم است.