Belirleyici Olmayan Sonlu Otomat
NDFA'da, belirli bir giriş sembolü için, makine, makinedeki durumların herhangi bir kombinasyonuna hareket edebilir. Başka bir deyişle, makinenin hareket ettiği kesin durum belirlenemez. Bu nedenle denirNon-deterministic Automaton. Sonlu sayıda duruma sahip olduğundan, makine denirNon-deterministic Finite Machine veya Non-deterministic Finite Automaton.
Bir NDFA'nın Biçimsel Tanımı
Bir NDFA, bir 5-tuple (Q, ∑, δ, q 0 , F) ile temsil edilebilir , burada -
Q sonlu bir durum kümesidir.
∑ alfabe adı verilen sonlu bir semboller kümesidir.
δgeçiş fonksiyonudur burada δ: Q × ∑ → 2 Q
(Burada Q (2 Q ) ' nun güç kümesi alınmıştır, çünkü NDFA durumunda, bir durumdan, Q durumlarının herhangi bir kombinasyonuna geçiş gerçekleşebilir)
q0herhangi bir girişin işlendiği ilk durumdur (q 0 ∈ Q).
F Q'nun (F ⊆ Q) nihai durum / durumları dizisidir.
Bir NDFA'nın Grafiksel Gösterimi: (DFA ile aynı)
Bir NDFA, durum diyagramı adı verilen dijital grafiklerle temsil edilir.
- Köşeler durumları temsil eder.
- Bir giriş alfabesiyle etiketlenmiş yaylar geçişleri gösterir.
- Başlangıç durumu, boş bir tek gelen yay ile gösterilir.
- Son durum çift dairelerle belirtilmiştir.
Example
Belirleyici olmayan sonlu bir otomat →
- Q = {a, b, c}
- ∑ = {0, 1}
- q 0 = {a}
- F = {c}
Geçiş işlevi δ aşağıda gösterildiği gibi -
| Mevcut durum | Giriş 0 için Sonraki Durum | Giriş 1 için Sonraki Durum |
|---|---|---|
| a | a, b | b |
| b | c | AC |
| c | M.Ö | c |
Grafik temsili aşağıdaki gibi olacaktır -
DFA ve NDFA
Aşağıdaki tablo, DFA ve NDFA arasındaki farkları listeler.
| DFA | NDFA |
|---|---|
| Bir durumdan geçiş, her giriş sembolü için belirli bir sonraki duruma geçiştir. Dolayısıyla buna deterministik denir . | Bir durumdan geçiş, her giriş sembolü için birden çok sonraki duruma olabilir. Dolayısıyla deterministik olmayan denir . |
| DFA'da boş dize geçişleri görülmez. | NDFA, boş dizi geçişlerine izin verir. |
| DFA'da geri izlemeye izin verilir | NDFA'da geri izleme her zaman mümkün değildir. |
| Daha fazla alan gerektirir. | Daha az alan gerektirir. |
| Bir dize, son bir duruma geçerse, DFA tarafından kabul edilir. | Bir dizi, olası tüm geçişlerden en az biri son durumda sona ererse, NDFA tarafından kabul edilir. |
Kabul Edenler, Sınıflandırıcılar ve Dönüştürücüler
Alıcı (Tanıyıcı)
Bir Boole işlevini hesaplayan bir otomat, bir acceptor. Bir alıcının tüm durumları, kendisine verilen girdileri ya kabul ediyor ya da reddediyor.
Sınıflandırıcı
Bir classifier ikiden fazla nihai duruma sahiptir ve sona erdiğinde tek bir çıkış verir.
Dönüştürücü
Mevcut girişe ve / veya önceki duruma göre çıktılar üreten bir otomat, transducer. Transdüserler iki tip olabilir -
Mealy Machine - Çıkış hem mevcut duruma hem de akım girişine bağlıdır.
Moore Machine - Çıkış sadece mevcut duruma bağlıdır.
DFA ve NDFA tarafından kabul edilebilirlik
DFA / NDFA, diziyi tamamen okuduktan sonra bir kabul durumunda (son durumlardan herhangi biri) başlangıç durumunda sona erdiğinde bir DFA / NDFA tarafından kabul edilir.
Bir S dizesi bir DFA / NDFA (Q, ∑, δ, q 0 , F) tarafından kabul edilir , ancak
δ*(q0, S) ∈ F
Dil L DFA / NDFA tarafından kabul edildi
{S | S ∈ ∑* and δ*(q0, S) ∈ F}
S ′ dizesi bir DFA / NDFA (Q, ∑, δ, q 0 , F) tarafından kabul edilmez , iff
δ*(q0, S′) ∉ F
DFA / NDFA tarafından kabul edilmeyen L ′ dili (kabul edilen L dilinin tamamlayıcısı)
{S | S ∈ ∑* and δ*(q0, S) ∉ F}
Example
Şekil 1.3'te gösterilen DFA'yı ele alalım. DFA'dan kabul edilebilir dizeler türetilebilir.
Yukarıdaki DFA tarafından kabul edilen dizeler: {0, 00, 11, 010, 101, ...........}
Yukarıdaki DFA tarafından kabul edilmeyen dizeler: {1, 011, 111, ........}