“Automata theory” dersini alan arkadaşların yakından bildikleri e’nfa (epsilon nondeterministic finite automata) dan dfa (deterministic finite automata) ya çevirme problemi vardır. Bu yazımda, bu problem için hazırlanmış nfa’yı dfa’ya çeviren bir  java projesini paylaşacağım.

Javada yazılmış bu program, elinizde mevcut olan bir epsilon nfa yı programa girerek dfa ye çevirmenizi ve dfa yı görsel olarak ekrana çizmenizi sağlamaktadır.

Programdan ekran görüntüleriyle örnek bir çeviri işlemi yapalım.

Bize verilen e’nfa şu şekilde olsun.

Bu örneği programa şu şekilde gireceğiz. Number of State bölümüne 0-10 tane state olduğu için 11 giriyoruz. Language bölümüne yukarıda ki örnekte  verilen dildeki karakterleri virgul ile ayırarak giriyoruz. a,b yazıyoruz ve create table butonuna tıklıyoruz.

Şimdi tabloyu yukarıdaki örnekte olduğu gibi dolduralım. States kolonuna state isimlerini, propert bölümüne start(başlangıç) ve accept(kabul) statelerini belirtiyoruz. Start ve Accept yerine kısaca “s” ve “a” da yazılabilir. Ayrıca bir start state aynı zamanda accept state ise virgul ile ayrılarak ikiside yazılabilir. Epsilon ile geçişleri ve dildeki karakterler ile geçişleri uygun olarak dolduruyoruz. Olmayanları boş bırakıyoruz.Aynı geçişte nfa özelliği sebebiyle birden çok state varsa virgül ile ayırarak yazabiliriz.

Şimdi convert dfa butonu ile çevirme (convert) işlemini yapabiliriz. Bu işlemi yaptığımızda arkada bir pencere daha açılacak ve o da yaratılan dfa nın görsel halini çizecek ekrana. Şu şekilde

Bu da ekran dfa nın çizilmiş hali.

Bu şekilde verilen bir enfa dan dfa ya çevirme işlemini gerçekleştirmiş olduk. Şimdi biraz kodu inceleyelim. Program dokuz tane class dan oluşmaktadır.

• DrawPanel (Çizim işlemini gerçekleştirmektedir.)
• Helper (Yardımcı fonksiyonlar içermektedir.)
• Main (Formumuzun classıdır)
• State (Kullanıcı tarafından girilen nfa statelerin tutulduğu class)
• StateDfa (Oluşturulan dfa statelerin tutuluduğu class)
• StateDfaList (Programın oluşturduğu dfa statelerin listesi)
• StateList (Kullanıcının girdiği nfa statelerin listesi)
• State_Relation (Nfa stateler arasındaki ilişkileri tutan class)
• State_Relation_Dfa (Dfa stateler arasındaki ilişkileri tutan class)

Programın genel anlamda izlediği algoritma şudur.

Programın çalışır halini buradan indirebilirsiniz.(program çalışmaz ise bilgisayarınızda bulunan java runtime environmenti jre7 ye yükseltmeniz gerekecektir),
kaynak kodlarını buradan indirebilirsiniz.

<<< Önceki: Basit!! bir C Sorusu

Sonraki: Android ve Php ile Basit Client-Server Uygulaması >>>