DFA Sadeleştirme [Minimum Durumlu DFA]

Yazar:


Daha önceden hiç aklımda yokken bir anlık bir karar ile arkadaşım Ece için hazırladığım bu içeriği, hazırladıktan sonra blogda paylaşmaya karar verdim. Umarım internette bu konuyu arayan birçok kişiye de faydalı olur.

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.





Hey!

Blogkafem'de okuduğunuz içeriklerle ilgili kişisel Twitter hesabım üzerinden benimle iletişme geçmek isterseniz Twitter adresim : www.twitter.com/aliarslan10

Sosyal medya hesabım dışında Blogkafem'de okumuş olduğun içerik ile ilgili belirtmek istediklerinizi aşağıdaki yorum formuna yazabilirsin. En kısa sürede dönüş yapacağımdan emin olabilirsin. :)

Okuduğunuz içerik faydalı olduysa #blogkafem etiketiyle okuduğunuz içeriğin linkini Twitter'da paylaşarak Blogkafem'e destek olabilirsiniz.

0 yorum:

Yorum Sayfası :



Yorum yaparken dikkat edilmesi gerekenler;

1. Yorum Formunu doldurduktan sonra Profil Seç -> ADI/URL bölümünden isminizi yazıp yorum yaparsanız size karşı bir hitap şeklimiz olur. (URL kısmını boş bırakabilirsiniz.)

2. Anonim olarak yaptığınız yorumlar "Adsız" olarak gözükmektedir.

3. Türkçe yazım ve dilbilgisi kurallarına uymaya özen gösteriniz.

4. Küfür,hakaret,mail adresi veya konu ile ilgisi olmayan reklam amaçlı website adresi içeren yorumlar yayınlanmamaktadır.

Custom Search

Kafemizde En Son Kim, Ne Demiş?

Kafeyi Dikizleyenler :)

Blog Istatistik

BLOGKAFEM.NET

© Copyright 2008-2016
Sitedeki yazıların her hakkı BLOGKAFEM.NET sitesine aittir.
Kopyalanması halinde lütfen kaynak gösteriniz.
DMCA.com Protection Status
Anasayfa | Hakkımızda | Bizden | Reklam | İletişim