✖

Düzenli Dillerin Farkı

L1, L2 iki düzenli dil olsun. Bunların farkı olan L = L1 ∖ L2 dilinin de düzenli bir dil olduğunu ispatlayacağız.

Fikir

Aslında ispatlanacak pek bir şey yok. Çünkü iki kümenin farkı için şu bağıntı geçerlidir:

L1∖L2=L1∩L2′,

burada L2′, L2 dilinin tümleyenidir. Düzenli dillerin kesişimi ve düzenli dilin tümleyeni bölümlerinden biliyoruz ki düzenli diller bu iki işleme göre kapalıdır. Yani dillerin kesişimini kabul eden bir otomat ve bir dilin tümleyenini kabul eden bir otomat kurabiliriz. Bu otomatları kullanarak L1 ∩ L2′ dilini kabul eden bir otomat kurabiliriz; bu dil ise aynı zamanda L1 ∖ L2 dilidir.

Örnek

Çift sayıda 1 içeren tüm sözcükleri kabul eden A1 otomatını ele alalım:

ve tek sayıda 0 içeren sözcükleri kabul eden A2 otomatını:

Bu dillerin farkını kabul eden bir otomat kuracağız. Bunun için A2 otomatının tümleyeni olan A2′ otomatına ihtiyacımız var. Kabul durumlarıyla kabul etmeyen durumları yer değiştirmemiz yeterli:

Şimdi L(A1) ve L(A2′) dillerinin kesişimini kabul eden A otomatını kurmamız yeterli:

Bölümler: Düzenli Dillerin Kapalılığı, Düzenli Dillerin Birleşimi, Düzenli Dillerin Kesişimi, Düzenli Dillerin Farkı, Düzenli Dilin Tümleyeni, Düzenli Dillerin Birleştirilmesi, Düzenli Dilin Kleene Kapanışı