„Nemdeterminisztikus véges állapotú gép” változatai közötti eltérés
| [nem ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a →Megvalósítása: elírás jav |
a kész |
||
1. sor:
A [[számítógép-tudomány]]ban
▲A [[számítógép-tudomány]]ban, a '''nemdeterminisztikus véges állapotú gép''' vagy a '''nemdeterminisztikus véges állapotú automata''', angol terminológával a ''nondeterministic finite state machine'' vagy ''nondeterministic finite automaton'' '''(NFA)''' egy [[véges állapotú gép]] ahol bármelyik állapot – bejövő szimbólum párhoz több következő állapot is tartozhat.
== Általános ismertetés ==
23 ⟶ 21 sor:
* (''S'') az állapotok véges halmaza
* (Σ) az ábécé-nek nevezett véges halmaz
* (''T'' : ''S'' × (Σ \{ε}) → ''P''(''S'')) az átmeneti függvény. Ez lehet olyan [[reláció]] is, ami nem [[függvény (matematika)|függvény]]
* ''s<sub>0</sub>'' a kitüntetett ''kezdeti'' (vagy ''indító'') ''állapotok'' halmaza (''s<sub>0</sub>'' <math>\subseteq</math> ''S'')
* (''A'' <math>\subseteq</math> ''S'') az [[elfogadó állapot]]ok halmaza
34 ⟶ 32 sor:
# ''r<sub>n</sub>'' <math>\in</math> ''A''.
Az automata a kezdő állapotból indulva olvassa a bejövő [[string]] szimbólumait, amelyek az adott ábécéhez kell, hogy tartozzanak. Az automata állapotát a T
Az automata által elfogadott stringek halmaza egy [[formális nyelv|nyelv]]i forma, az a nyelv, amelyet az NFA felismer. Ez a nyelv egy
[[szabályos nyelv]].
Minden NFA-hoz található egy [[determinisztikus véges állapotú gép]] (DFA), amely ugyanazt a nyelvet fogadja el.
== Megvalósítása ==
| |||