حل تمرین نظریه محاسبات/فصل اول/حل تمرین ۱-۱۳
تمرین ۱-۱۳
تمرین
ویرایشعبارات منظمی بنویسید که زبانهای تمرین 4-1 را تولید کند.
(a زبانی که با 1 شروع شود و با 0 خاتمه یابد.
(b زبانی که شامل حداقل 3 تا 1 باشد.
(c زبانی که شامل زیررشته 0101 باشد، مثلا x0101y برای هر x و y
(d زبانی که طول آن حداقل 3 باشد و سومین نماد آن 0 باشد.
(e زبانی که با 0 شروع شود و طول فرد داشته باشد یا با 1 شروع شود و طول زوج داشته باشد.
(f زبانی که شامل زیررشته 110 نباشد.
(g زبانی که طول آن حداکثر 5 باشد.
(h زبانی که همه رشته ها را می پذیرد به غیر از 11 و 111
(i زبانی که هر موقعیت فرد آن 1 باشد.
(j زبانی که شامل حداقل دو عدد 0 و حداکثر یک عدد 1 باشد.
(k زبانی که شامل مجموعه 0 و تهی باشد.
(l زبانی که شامل تعداد زوجی 0 و دقیقا دو عدد 1 باشد.
(m زبان ماشین تهی
(n زبانی که همه رشته ها را می پذیرد به جز رشته تهی
حل
ویرایشa. 1 Σ* 0
b. Σ* 1 Σ* 1 Σ* 1 Σ*
c. Σ* 0101 Σ*
d. Σ Σ 0 Σ*
e. 0 (Σ Σ)* + 1 (Σ Σ)* Σ
f. (00*(10)*)* 1* + ((10)* 0*)* + ((10)* 0* 10)* + (10)* 1* + 0* + 1*
g. (Σ + λ) (Σ + λ) (Σ + λ) (Σ + λ) (Σ + λ)
h. λ + Σ + 0 Σ* + 10 Σ* + 110 Σ* + Σ4 Σ*
i. 1 + (1 Σ)* + (1 Σ)*1 + 1(Σ 1)*
j. 000* + 10*00 + 0*1000* + 0*0100* + 0*0010*
k. λ + 0
l. 1*(00)*1* + 0*10*10*
m . Ǿ
n. Σ+