2.1 DFA Nedir ?

DFA¹ (Deterministic Finite Accepter) beşli ifadeden oluşturarak tanımlanır.

M = (Q, , , q0, F) Öyle ki:

• Q , nodların sonlu kümesidir,
• alfabe içindeki harflerden oluşan sonlu bir kümedir,
• : Q Q geçiş fonksiyonudur,
• q0 Q başlangıç durumudur,
• F Q sonlu nodlar kümesidir.

DFA mekanızması nasıl çalışır ?

DFA'de bir kelimenin doğru olup olmadığına bakmak için
başlangıç nodundan (Genellikle 1 numaralı noddur) ve kelimenin
ilk harfinden başlanır. İçinde bulunan noddayken elimizdeki harf
hangi noda gidiyorsa o noda varılır. Aranan kelimenin bir sonraki
harfine bakılır ve vardığımız nodda, elimizdeki harf ile hangi noda
gittiğine bakılır ve o noda gidilir. Kelimenin son harfine vardığımızda
eğer içinde bulunduğumuz nod sonlu bir nod (sonlu nodlar çift çember
ile gösterilir) ise kelime doğrudur.

Örnek bir DFA

Aşağıdaki şekilde (Şekil 1) örnek bir DFA'i görebilirsiniz. Bu DFA,
yanyana üç sıfırı içermeyen ikilik alfabeyi tanımlar. Başlangıç
nodu olan 1 numaralı noddan başlayıp örnek olarak "001"
kelimesinin doğru olup olmadığına bakalım. Kelimemizin ilk
harfini ,"0", alıyoruz. 1 numaralı noddayken "0" harfi ile 2
numaralı noda gittiğini görüyoruz. Kelimenin bir sonraki harfini ,
"0", alıyoruz. 2. noddayken "0"'ın 3 numaralı noda gittiğini görüyoruz.
Kelimenin son harfi olan "1"'i alıyoruz ve 3.noddayken "1" harfi ile
1 numaralı noda gittiğini görüyoruz. Kelimedeki "001", harflerin
tamamı bittiğine göre içinde durduğumuz nodun (1 nolu nod) sonlu
olup olmadığına bakıyoruz. Çift çemberle çevrili olduğunu görüp sonlu
olduğunu anlıyoruz. Sonlu bir nodda durduğumuza göre bu kelime doğrudur.



Şekil 1: Örnek bir DFA

Şekil 1'deki DFA basit bir DFA'dir. Tabi ki Türkçe gibi bir dil için çok
daha karmaşık bir DFA'e ihtiyacımız olacağı kesindir. Daha fazla bilgi
için otomata teorisi ve formal diller hakkında araştırma yapabilirsiniz.