2Deterministic Finite Automaton (DFA) Read only HeadFinite Control
3DFA Bir DFA şu beşliden oluşur: Sonlu sayıda elemana sahip durumlar kümesi1 adet başlangıç durumu (özel durum-initial state)Kabul durumları kümesi (0 yada daha fazlasayıda)Giriş simgelerinden oluşan ve sonlu sayıda elemanlı alfabe (input alphabet)Geçiş tablosu(Durum, simge) -> sonraki durum
4DFA nasıl çalışır? Makine Şerit modeli Şeritte bir giriş katarı vardırDFA çalışmaya başlangıç durumu ile başlar.Okuyucu kafa en sol hücrededir.DFA katarın tamamını okuyana kadar bir döngüye girer.Her adımda, DFA, geçiş fonksiyonuna göre okunan simgeye göre yeni bir duruma geçer.(Durum-s, simge) -> sonraki durums – o anki durum -okuyucu kafanın okuduğu simgeBütün katar okunduğunda eğer bir kabul durumunda kalınmışsa katar kabul edilir.Finite Control
5DFA nasıl çalışır? Giriş katarı okunduktan sonra, Eğer DFA kabul durumunda ise, giriş katarı kabul edilir.Eğer DFA bir kabul durumunda değilse, katarı reddedilir.DFA’nın dili: DFA tarafından kabul edilen bütün katarların kümesidir.
26Teorem:Tanım: Eğer bir dili kabul eden bir DFA varsa o dil regüler bir dildir.Örnekler:{}*{w Є {a,b}* | w’nin ikinci sembolü a’dır}{w in {a,b}* |w’nin sondan ikinci simgesi a’dır}{w in {0,1}* | w 010’i bir alt katar olarak içerir.}