logo

TechCodeview

NFA (nedeterministiniai baigtiniai automatai)

  • NFA reiškia nedeterministinius baigtinius automatus. Nurodytai įprastai kalbai lengva sukurti NFA nei DFA.
  • Baigtiniai automatai vadinami NFA, kai yra daug kelių konkrečiam įėjimui iš dabartinės būsenos į kitą būseną.
  • Kiekviena NFA nėra DFA, bet kiekviena NFA gali būti išversta į DFA.
  • NFA apibrėžiamas taip pat kaip DFA, tačiau su toliau nurodytomis dviem išimtimis jame yra kelios kitos būsenos ir ε perėjimas.

Toliau pateiktame paveikslėlyje matome, kad iš įvesties a būsenos q0 yra dvi kitos būsenos q1 ir q2, panašiai, iš q0 įvesties b, kitos būsenos yra q0 ir q1. Taigi nėra nustatyta ar nustatyta, kur eiti toliau su tam tikra įvestimi. Todėl šis FA vadinamas nedeterministiniais baigtiniais automatais.

Nedeterministiniai baigtiniai automatai

Oficialus NFA apibrėžimas:

NFA taip pat turi penkias būsenas, tokias pat kaip DFA, bet su skirtinga perėjimo funkcija, kaip parodyta toliau:

java pridėti prie masyvo 
 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup>

kur,

 Q: finite set of states &#x2211;: finite set of the input symbol q0: initial state F: final state &#x3B4;: Transition function

Grafinis NFA vaizdavimas

NFA gali būti pavaizduotas digrafais, vadinamais būsenos diagrama. Kuriame:

  1. Valstybę vaizduoja viršūnės.
  2. Lankas, pažymėtas įvesties simboliu, rodo perėjimus.
  3. Pradinė būsena pažymėta rodykle.
  4. Galutinė būsena žymima dvigubu apskritimu.

1 pavyzdys:

 Q = {q0, q1, q2} &#x2211; = {0, 1} q0 = {q0} F = {q2}

Sprendimas:

Perėjimo schema:

dirbtinis intelektas ir intelektualūs agentai
Nedeterministiniai baigtiniai automatai

Perėjimo lentelė:

Dabartinė valstybė Kita 0 įvesties būsena Kita 1 įvesties būsena
→q0 q0, q1 q1
q1 2 k q0
*2 k 2 k q1, q2

Aukščiau pateiktoje diagramoje matome, kad kai dabartinė būsena yra q0, 0 įėjime kita būsena bus q0 arba q1, o 1 įėjime kita būsena bus q1. Kai dabartinė būsena yra q1, 0 įėjime kita būsena bus q2, o 1 įėjime kita būsena bus q0. Kai dabartinė būsena yra q2, 0 įėjime kita būsena yra q2, o 1 įėjime kita būsena bus q1 arba q2.

2 pavyzdys:

NFA su ∑ = {0, 1} priima visas eilutes su 01.

Sprendimas:

Nedeterministiniai baigtiniai automatai

Perėjimo lentelė:

Dabartinė valstybė Kita 0 įvesties būsena Kita 1 įvesties būsena
→q0 q1 e
q1 e 2 k
*2 k 2 k 2 k

3 pavyzdys:

NFA su ∑ = {0, 1} ir priimti visą eilutę, kurios ilgis yra bent 2.

pridedant eilutę Java

Sprendimas:

Nedeterministiniai baigtiniai automatai

Perėjimo lentelė:

Dabartinė valstybė Kita 0 įvesties būsena Kita 1 įvesties būsena
→q0 q1 q1
q1 2 k 2 k
*2 k e e