DFA Sadeleştirme [Minimum Durumlu DFA]

Karmaşık durumdaki DFA'ların minimumu hale getirilmesi durumuna, DFA sadeleştirilme denmektedir. Aşağıdaki karmaşık durumlu DFA'dan yola çıkarak bunun en sade halini elde etmeye çalışacağız.

Yukarıdaki ekran görüntüsünü baz alarak sadeleştirme işlemini 2 adımda yapacağız. 

1. adım'da erişilemez durumları ortadan kaldıracağız. Ben erişilemez durumları, aşağıdaki ekran görüntüsünden de görüleceği üzere numaralandırdım.

Peki erişilemez durumlara nasıl karar verdik? Onu da şöyle anlıyoruz.
İlk önce hiç "ok işareti" gelmeyen durumları DFA'dan kaldırıyoruz.
Yani önce, 1,3 ve 5 durumlarını DFA'dan kaldırıyoruz. Bu kaldırma işleminden sonra DFA'yı tekrar inceliyoruz. 1,3 ve 5'i kaldırma işleminden sonra 2 ve 4'e de artık ok gelmediğini görüyoruz. O halde artık 2 ve 4 durumları da erişilemez durum olmuştur. Onları da kaldırıyoruz.

Yani şeklimiz artık şöyle olmuştur :

Erişilemez durumları ortadan kaldırdıktan sonra, üstteki ekran görüntüsünde de görüleceği üzere otomat 2 farklı guruba ayrılmış. Guruplara ayırma işlemi aynı zamanda DFA sadeleştirme işleminin 2. adımı olmuş oluyor.

Guruplama işlemini yaparken ise "kabul edilebilir durumlar" ve "kabul edilemez" durumlar olmak üzere ayırma işlemini yapıyoruz. Ben "kabul edilebilir" durumların olduğu guruba "Gurup 1" diyorum. "Kabul edilemez" durumların olduğu guruba da "Gurup 2" diyorum.

Bir durumun hem "a"sı veya "b"si farklı bir guruba gidiyorsa eğer, bu durum için farklı bir gurup yaparız. Diğer durumlar ise aynı gurupta kalırlar. Bu dediğim şey sorudan soruya değişir. Kimi sorularda her iki harfin farklı guruba gitmesi ile farklı bir gurup yapmak gerekir. Fakat bizim bu örneğimize göre sadece "b" harfinin farklı bir guruba gitmesi, ayrı bir gurup yapmak için yeterli olacaktır. Resimdeki örneği  incelediğimiz zaman zaten, iki gurup arası bağlantı "b" geçişleri ile olmaktadır. Şimdi ise tek tek hangi durum hangi guruba gitmiş inceleyelim. Bu incelemeyi "Gurup 2" üzerinden yapacağız. Yani, "kabul edilemez" durumların olduğu gurubu inceleyip, sadeleştirme işlemini de orada yapacağız.

Durumları inceleyelim.

2 numaralı duru için :
a harfi gelince 6'ya gitmiş. Yani Gurup 2'de kalmaya devam ediyoruz.
b harfi gelince 5'e gitmiş. Yine Gurup 2'de kalıyoruz.

3 numaralı durum için :
a harfi gelince 2'ye gitmiş. Yani Gurup 2'de kalıyoruz.
b harfi gelince 5 numaralı duruma gidiyoruz.  Yine Gurup 2'de kalıyoruz.

5 numaralı durum için :
a harfi gelince 2'ye gidiyor. Gurup 2'de kalıyoruz.
b harfi gelince 4 nolu duruma gidiyor. Yani Gurup 1'e gidiyoruz.

6 numaralı durum için :
a harfi gelince 3'e gitmiş. Yani Gurup 2'de kalıyoruz.
b harfi gelince 5 nolu duruma gidiyor. Gurup 2'de kalıyoruz.

7 numaralı durum için :
a harfi gelince 6'ya gitmiş. Yani Gurup 2'de kalıyoruz.
b harfi gelince 5'e gidiyoruz. Gurup 2'de kalmaya devam ediyoruz.

Durumları inceledik. Peki ayırma işlemini nasıl yapacağız?
Bir önceki paragrafta da dediğim gibi bu örneğimize göre, "b" iki gurup arası geçiş harfi olduğu için 2. grubu bölmek için "b" harfine bakacağız. Yani 2. grup da kendi içinde 2 parçaya bölüneceği zaman "b" kriterine göre şu şekilde bölünecektir :

• 1) b ile ilk gruba gidenler
• 2) b ile kendi içinde kalanlar

Bu bilgiyi baz alırsak eğer, o halde yaptığımız durum incelemelerine göre "5" farklı bir gurup olacaktır. 2, 3, 6, 7 durumları ise ayrı bir gurup olacaktır.

Şu şekilde : 

"5" in olduğu guruba da "Gurup 3" diyelim. Üstteki ekran görüntüsünde yine "Gurup 2" incelenir. Daha fazla bölnüp bölünmediğine yani sadeleştirilip, sadeleştirilmediğine bakılır. Bu soruda "Gurup 2" daha da fazla sadeleştirilemediği için, DFA'nın en sade hali üstteki resimdir diyebiliriz. Son olarak ise aynı gurupta olanları aynı durum içine yazacağız ve işlemimizi sonlandıracağız. Yani DFA'mızın sadeleştirilmiş son hali şöyle olacaktır :

Konu ile ilgili aklınıza takılan yerler olursa eğer, aşağıdaki yorum formuna yazarak bana bildirebilirsiniz. İyi çalışmalar.