5 Belirlenimli Olmayan Sonlu Otomat

Belirlenimli Olmayan Sonlu Otomat (BOSO) ingilizcesi Non Deterministic finite automaton (N-DFA)’dır.

BSO’dan farklı olarak BOSO’da bir durumdan 0 çıktı, birden fazla çıktı olabilir.
Aynı zaman \(\epsilon\) ile geçiş yapılabilir.

5.1 Örnek BOSO Diyagram

5.2 Giriş BOSO Örnekler

Özel bir desen ile biten dizgiler

Dil: \(L = \{ w \in \{0, 1\}^* \mid \text{w kelimesi 01 ile biter }\}\)

Sondan \(k\). Sembol

Sondan \(k\). sembolün 1 olup olmadığının belirlenmesini ele alalım (örneğin, \(k=3\)):

girdiler: ... 0  1  0  1  1
                (*)
                Bu 1 sondan 3 mu?

Daha kolay örnek: Sondan 2. Sembol 1 olsun. Yani 01 veya 11 ile biten dizgiler.

DFA, NFA

içinde spesifik alt dizgi olan dizgiler. örneğin içinde 101 olan dizgiler.
Özel alt dizgi birden fazla olabilir.

\(\Sigma = \{0, 1\}\) alfabesi üzerinde tanımlı \(L = \{w \mid w = (101)^n, \, n \ge 1\}\) dilini tanıyan bir BOSO ve bir BSO tasarlayın.

Bu dil, sadece bir veya birden fazla kez peş peşe gelen “101” dizilerini kabul eder (örneğin: 101, 101101, 101101101 kabul edilir; boş kelime \(\epsilon\), 10, 1011 vb. reddedilir).

5.3 Karşılaştırma tablosu

Özellik	Belirlenimli Sonlu Otomat (BSO-DFA)	Belirlenimli Olmayan Sonlu Otomat (BOSO-NFA)
Sembol başına geçişler	Alfabedeki her bir sembol için tam olarak 1 tane	0, 1, or birden fazla tercih
Boş hareket (\(\epsilon\))	İzin verilmez	Verilir (\(\epsilon\)-transitions)
Mevcut Durum	Daima 1 durumda	Aynı anda birden fazla durumda olabilir.
Tasarım	Daha zordur. Tüm sınır durumları modellemek gerekir.	Daha kolay, sadece başarılı durumlarda odaklanın.
Durum sayısı	Üstel olarak daha büyük olabilir (\(O(2^n)\))	Genellikle daha az (\(O(n)\))
Uygulama Hızı	Hızlı: Karakter/girdi başına \(O(1)\) arama character	Daha yavaş simule edilir.: her girdi/karakter için \(O(\vert{}Q\vert{}^2)\) arama
İfade Gücü	Aynıdır	Aynıdır (Her NFA bir DFA’ya çevrilebilir.)