Ero sivun ”Äärellinen automaatti” versioiden välillä

Epädeterministinen äärellinen automaatti, lyh. ''NFA'' (''engl. non-deterministic finite-state automaton'') on tila-automaatti, jossa kustakin tilasta voi olla samalla aakkosella tilasiirtymiä useampaan kuin yhteen tilaan. Nimessä oleva osa epädeterministinen tulee siitä, että saman ratkaisun tuottavat tilat voidaan käydä lävitse useampaa kuin yhtä polkua pitkin kulkemalla. NFA:n ilmaisuvoima ei ole suurempi kuin DFA:n, mutta tietyntyyppiset DFA:t voi ilmaista huomattavasti yksinkertaisemmilla tilakoneilla NFA:ta käyttäen. Mielivaltaisesta epädeterministisestä äärellisestä automaatista voidaan muodostaa algoritmisesti saman kielen hyväksymä vastaava deterministinen automaatti.
 
NFA:ssa DFA:n osittainen tilasiirtymäfunktio δ korvataan tilasiirtymärelaatioilla, joka merkitään Δ. NFA on ''ystävällisesti epädeterministinen'', ja hyväksyy merkkijonon α, jos on olemassa polku q̂─α→q, jossa q ⊂ F. Eli valitsee aina hyväksyntään johtavan tavan jos sellainen on olemassa.
 
== Sovellutuksia ==