Ero sivun ”Äärellinen automaatti” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Rivi 50:
== Epädeterministinen äärellinen automaatti ==
[[Kuva:NFAexample.svg|thumb|Esimerkki epädeterministisestä äärellisestä automaatista.]]
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.
| |||