TechCodeview

• NFA, deterministik olmayan sonlu otomata anlamına gelir. Belirli bir normal dil için bir NFA oluşturmak DFA'dan daha kolaydır.
• Mevcut durumdan bir sonraki duruma kadar belirli girdiler için birçok yol mevcut olduğunda sonlu otomatlara NFA adı verilir.
• Her NFA, DFA değildir ancak her NFA, DFA'ya çevrilebilir.
• NFA, DFA ile aynı şekilde tanımlanır ancak aşağıdaki iki istisna dışında, birden fazla sonraki durumu içerir ve ε geçişini içerir.

Aşağıdaki görüntüde, a girişi için q0 durumundan sonraki iki durumun q1 ve q2 olduğunu, benzer şekilde b girişi için q0 durumundan sonraki durumların q0 ve q1 olduğunu görebiliriz. Bu nedenle belirli bir girdiyle bir sonraki nereye gidileceği sabitlenmez veya belirlenmez. Dolayısıyla bu FA'ya deterministik olmayan sonlu otomata adı verilir.

NFA'nın resmi tanımı:

NFA ayrıca aşağıda gösterildiği gibi DFA ile aynı ancak farklı geçiş işlevlerine sahip beş duruma sahiptir:

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

Neresi,

dizeye boolean

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Bir NFA'nın Grafiksel Gösterimi

Bir NFA, durum diyagramı adı verilen digraflarla temsil edilebilir. Hangisinde:

1. Durum köşelerle temsil edilir.
2. Giriş karakteriyle etiketlenen yay, geçişleri gösterir.
3. Başlangıç ​​durumu bir okla işaretlenmiştir.
4. Son durum çift daire ile gösterilir.

Örnek 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

Çözüm:

Geçiş diyagramı:

Geçiş Tablosu:

Yukarıdaki şemada, mevcut durum q0 olduğunda, 0 girişinde bir sonraki durumun q0 veya q1 olacağını ve 1 girişinde bir sonraki durumun q1 olacağını görebiliriz. Mevcut durum q1 olduğunda, 0 girişinde bir sonraki durum q2 olacak ve 1 girişinde bir sonraki durum q0 olacaktır. Mevcut durum q2 olduğunda, 0 girişindeki sonraki durum q2, 1 girişindeki sonraki durum ise q1 veya q2 olacaktır.

Örnek 2:

∑ = {0, 1} olan NFA, 01 olan tüm dizeleri kabul eder.

Çözüm:

Geçiş Tablosu:

Örnek 3:

∑ = {0, 1} olan NFA ve en az 2 uzunluktaki tüm dizeleri kabul edin.

Çözüm:

Geçiş Tablosu: