TechCodeview

• NFA apzīmē nedeterministiskus galīgus automātus. Konkrētajai parastajai valodai ir viegli izveidot NFA, nevis DFA.
• Galīgos automātus sauc par NFA, ja ir daudz ceļu konkrētai ievadei no pašreizējā stāvokļa uz nākamo stāvokli.
• Katrs NFA nav DFA, taču katru NFA var tulkot DFA.
• NFA ir definēts tāpat kā DFA, bet ar diviem tālāk norādītajiem izņēmumiem tajā ir vairāki nākamie stāvokļi un ir ε pāreja.

Nākamajā attēlā redzams, ka no stāvokļa q0 ievadei a ir divi nākamie stāvokļi q1 un q2, līdzīgi, no q0 ieejai b, nākamie stāvokļi ir q0 un q1. Tādējādi nav noteikts vai noteikts, ka ar konkrētu ievadi kur iet tālāk. Tāpēc šo FA sauc par nedeterministiskiem galīgiem automātiem.

Oficiālā NFA definīcija:

NFA ir arī pieci stāvokļi, kas ir tādi paši kā DFA, bet ar atšķirīgu pārejas funkciju, kā parādīts tālāk:

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

kur,

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

NFA grafisks attēlojums

NFA var attēlot ar digrāfiem, ko sauc par stāvokļa diagrammu. Kurā:

1. Valsts tiek attēlota ar virsotnēm.
2. Loka, kas apzīmēta ar ievades rakstzīmi, parāda pārejas.
3. Sākotnējais stāvoklis ir atzīmēts ar bultiņu.
4. Galīgo stāvokli apzīmē ar dubulto apli.

1. piemērs:

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

Risinājums:

Pārejas diagramma:

Pārejas tabula:

Iepriekš redzamajā diagrammā redzams, ka, ja pašreizējais stāvoklis ir q0, ieejā 0 nākamais stāvoklis būs q0 vai q1, un 1 ieejā nākamais stāvoklis būs q1. Ja pašreizējais stāvoklis ir q1, ieejā 0 nākamais stāvoklis būs q2 un 1 ieejā nākamais stāvoklis būs q0. Ja pašreizējais stāvoklis ir q2, 0 ieejā nākamais stāvoklis ir q2, un 1 ieejā nākamais stāvoklis būs q1 vai q2.

2. piemērs:

NFA ar ∑ = {0, 1} pieņem visas virknes ar 01.

Risinājums:

Pārejas tabula:

3. piemērs:

NFA ar ∑ = {0, 1} un pieņem visas virknes, kuru garums ir vismaz 2.

Risinājums:

Pārejas tabula: