Deterministik çevrimsiz sonlu durum otomatı

Bilgisayar biliminde, **deterministik çevrimsiz sonlu durum otomatı (DAFSA)**, bir dizeler kümesini temsil eden ve belirli bir dizeyin kümeye ait olup olmadığını, dize uzunluğuna orantılı sürede test etmeye olanak sağlayan bir veri yapısıdır. Bu tür otomatları inşa etmek ve sürdürmek için algoritmalar geliştirilmiştir ve bu algoritmalar, yapıyı minimum düzeyde tutacak şekilde çalışır. DAFSA, Yönlendirilmiş Çevrimsiz Kelime Grafiği (DAWG) olarak bilinen bir veri yapısının yeniden keşfidir, ancak aynı ad, daha önce son ek otomatı ile ilişkili farklı bir veri yapısına da verilmiştir.

DAFSA, tek bir kaynak köşesi (gelen kenarı olmayan bir köşe) olan yönlendirilmiş döngüsüz bir graf biçimindeki, sonlu durum tanıyıcı yapısının özel bir durumudur. Bu grafikte her kenar bir harf veya sembolle etiketlenmiştir ve her köşenin, her olası harf veya sembol için en fazla bir giden kenarı vardır. DAFSA'nın temsil ettiği dizeler, kaynak köşeden herhangi bir alıcı köşeye (çıkış kenarı olmayan köşe) giden yollardaki sembollerle oluşturulur. Aslında, bir deterministik sonlu durum otomatı, ancak ve ancak sonlu bir dize kümesini tanıyorsa döngüsüzdür.

## Tarihçe
Blumer ve arkadaşları, *Yönlendirilmiş Çevrimsiz Kelime Grafiği (DAWG)* terimini ilk kez 1983 yılında tanımlamıştır. Appel ve Jacobsen, 1988 yılında aynı ismi farklı bir veri yapısı için kullanmıştır. Önceki çalışmalardan bağımsız olarak, Daciuk ve arkadaşları, bu ikinci veri yapısını 2000 yılında yeniden keşfetmiş, ancak ona *DAFSA* adını vermiştir.

## Trie’larla Karşılaştırma
Aynı düğümlerin birden fazla yol aracılığıyla erişilebilir olmasına izin vererek, bir *DAFSA*, yakından ilişkili olan *trie* veri yapısına göre önemli ölçüde daha az düğüm kullanabilir. Örneğin, İngilizce'deki "tap", "taps", "top" ve "tops" sözcüklerini ele alalım. Bu dört sözcüğü temsil eden bir trie, her bir sözcüğün öneklerinden veya sözcüğün ardından gelen dize sonu işaretçisinden oluşan toplam 12 düğüm içerir. Buna karşılık bir *DAFSA*, aynı dört sözcüğü yalnızca altı düğüm kullanarak temsil edebilir: *v<sub>i</sub>* olmak üzere 0 ≤ *i* ≤ 5. Bu yapıda, *v*0'dan *v*1'e "t" harfiyle etiketli bir kenar bulunur. *v*1'den *v*2'ye "a" ve "o" harfleriyle etiketlenmiş iki ayrı kenar vardır. Ardından, *v*2'den *v*3'e "p" harfiyle, *v*3'ten *v*4'e "s" harfiyle etiketli kenarlar bulunur. Son olarak, hem *v*3 hem de *v*4'ten *v*5'e, dize sonunu belirten işaretle etiketlenmiş kenarlar çıkar.

Bu yapı, bellek kullanımı ile işlevsellik arasında bir ödünleşim ortaya koyar. Standart bir *DAFSA*, bir kelimenin veri yapısında bulunup bulunmadığını belirleyebilir; ancak bu kelimeyle ilişkili ek bilgilere erişim sunamaz. Buna karşın, bir trie yapısı bu tür yardımcı bilgileri her düğüme eklemeye olanak tanır.

DAFSA ile trie arasındaki temel fark, dizeleri depolarken son ek (suffix) ve iç içe (infix) tekrarların ortadan kaldırılmasıdır. Trie veri yapısı, tüm ortak öneklerin paylaştırılması sayesinde önek (prefix) tekrarını ortadan kaldırır. Örneğin, "doctors" ve "doctorate" kelimeleri arasında "doctor" öneki ortaktır ve trie bunu yalnızca bir kez depolar. DAFSA ise yalnızca önekleri değil, aynı zamanda ortak son ekleri de paylaştırır; bu, son ek kümeleri benzer olan kelimeler için geçerlidir. Bu özellik, özellikle İngilizce gibi çok sayıda ortak önek ve son ek içeren dillerdeki sözlük kümelerinde, bellek kullanımında önemli ölçüde azalma sağlar.

Bir DAFSA'daki uç (terminal) düğümlere birden fazla farklı yoldan erişilebildiği için, her bir yol ile ilişkili yardımcı bilgileri — örneğin bir kelimenin İngilizce dilindeki kullanım sıklığı gibi — doğrudan depolamak mümkün değildir. Ancak, her düğümde bu noktadan geçen benzersiz yolların sayısı saklanırsa, bu bilgi bir kelimenin dizinini bulmak ya da bir dizine karşılık gelen kelimeyi elde etmek için kullanılabilir. Bu durumda yardımcı bilgiler bir dizi (array) içinde tutulabilir.

## Kaynakça

* 
*  — Veri yapısına erken dönemde yapılan atıflardan biridir.
*

* 

* 
— Python dilinde geliştirilmiş bir açık kaynak uygulama.

## Dış Bağlantılar

* Yönlendirilmiş Çevrimsiz Kelime Grafiği (DAWG) – JohnPaul Adamovsky, bir dizi tamsayı kullanarak bir DAFSA'nın nasıl inşa edileceğini anlatmaktadır. 
* Caroline Kelime Grafiği (CWG) – JohnPaul Adamovsky, bir DAFSA hash fonksiyonu inşa etmek için yeni bir kodlama yöntemi kullanarak birden fazla tamsayı dizisi ile nasıl yapılacağını öğretmektedir.