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

تمرین ۱-۱۳

تمرین

عبارات منظمی بنویسید که زبانهای تمرین 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. Σ+