A dili düzenli (regular) ise B dili düzenli ise AUB’nin düzenli olduğunu ispatlayınız?

A dili düzenli (regular) ise B dili düzenli ise AUB’nin düzenli olduğunu ispatlayınız?

İki düzenli dilin birleşimi düzenlidir. Bunu örnekle ispat edelim:

Örneğin:
RE1=a(aa)*
RE2=(aa)*
olsun.

RE1’e ait dil: L1={a,aaa,aaaaa,…} – 1,3,5,7,9 şeklinde tek sayıda a ifadelerinin olduğu bir dil
RE2’ye ait dil: L2={null,aa,aaaa,aaaaaa,…} – Boş,2,4,6,8 şeklinde çift sayıda a ifadelerinin olduğu bir dil
L1UL2={null, a,aa,aaa,aaaa,aaaaa,aaaaaa,…} – Boş, 1,2,3,4,5,6 şeklinde a ifadelerinin bulunduğu bir bil oluşur.
Bu dil RE(L1UL2)=a* ile ifade edilebildiğinden düzenlidir.

Aybüke BABADAĞ’ın cevabı:

aybuke-babadag-duzenli-dillerin-birlesimi

3 Yorum

  1. Bunu ıspatlamak için örnek kullandın..
    Bence böyle yaparız. varsayalım regular dil A1’i tanıyan bir NFA N1 olsun. regular dil A2’yi tanıayan bir NFA N2. Birleşik N A1UA2’yi tanır olsun. Proof by Construction: N1=(Q1,E,d1,q1,F1), N2=(Q2,E,d2,q2,F2),
    İnşaat N=(Q,E,d,q,F)
    Q=Q1UQ2Uq0, F=F1UF2
    d=

  2. Evet eksik kalmiş…. bu sadece proof idea

Yorum Yapın