حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۳۷
سوال)
نشان دهید زبان { 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 برای پذیرفتن این زبان بدست آوردیم پس این زبان منظم است.