TechCodeview

• NFA on lyhenne sanoista ei-deterministinen äärellinen automaatti. Tietylle tavalliselle kielelle on helppo rakentaa NFA kuin DFA.
• Äärillisiä automaatteja kutsutaan NFA:ksi, kun tietylle syötteelle on olemassa monia polkuja nykyisestä tilasta seuraavaan tilaan.
• Jokainen NFA ei ole DFA, mutta jokainen NFA voidaan kääntää DFA:ksi.
• NFA määritellään samalla tavalla kuin DFA, mutta seuraavilla kahdella poikkeuksella se sisältää useita seuraavan tiloja ja se sisältää ε-siirtymän.

Seuraavassa kuvassa nähdään, että tilasta q0 syötteelle a on kaksi seuraavaa tilaa q1 ja q2, vastaavasti tulon b tilasta q0 seuraavat tilat ovat q0 ja q1. Näin ollen ei ole kiinteää tai määrättyä, että tietyllä syötteellä minne mennä seuraavaksi. Tästä syystä tätä FA:ta kutsutaan ei-deterministisiksi äärellisiksi automaateiksi.

NFA:n virallinen määritelmä:

NFA:lla on myös viisi tilaa, jotka ovat samat kuin DFA:lla, mutta eri siirtymätoiminnoilla, kuten seuraava:

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

missä,

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

NFA:n graafinen esitys

NFA voidaan esittää digrafeilla, joita kutsutaan tilakaavioiksi. Jossa:

1. Valtiota edustavat kärjet.
2. Syötemerkillä merkitty kaari näyttää siirtymät.
3. Alkutila on merkitty nuolella.
4. Lopullinen tila on merkitty kaksoisympyrällä.

Esimerkki 1:

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

Ratkaisu:

Siirtymäkaavio:

Siirtymätaulukko:

Yllä olevasta kaaviosta nähdään, että kun nykyinen tila on q0, tulossa 0 seuraava tila on q0 tai q1 ja 1 sisääntulossa seuraava tila on q1. Kun nykyinen tila on q1, tulossa 0 seuraava tila on q2 ja 1 sisääntulossa seuraava tila on q0. Kun nykyinen tila on q2, 0-tulossa seuraava tila on q2 ja 1-tulossa seuraava tila on q1 tai q2.

Esimerkki 2:

NFA, jossa on ∑ = {0, 1}, hyväksyy kaikki merkkijonot, joissa on 01.

Ratkaisu:

Siirtymätaulukko:

Esimerkki 3:

NFA, jossa ∑ = {0, 1} ja hyväksy kaikki merkkijonot, joiden pituus on vähintään 2.

Ratkaisu:

Siirtymätaulukko: