Poopćeni nedeterministički konačni automat
U teoriji izračunljivosti, poopćeni nedeterministički konačni automat (PNKA) je NKA u kojem svaki prijelaz može biti označen regularnim izrazom. PNKA čita blokove znakova (simbola) sa ulaza koji sačinjavaju niz znakova (string) kao što definira regularni izraz nad prijelazom.
Formalna definicija[uredi]
PNKA se može definirati kao uređena petorka (S, Σ, T, s, a), koju čine:
- konačan skup stanja (S)
- konačan skup stanja zvan abeceda (Σ)
- funkcija prijelaza (T : (S -{a}) × (S - {s}) → R)
- početno (ili inicijalno) stanje (s ∈ S)
- prihvatljivo stanje (a ∈ S)
gdje je R skup svih regularnih izraza nad abecedom Σ.
DKA i NKA se mogu lako pretvoriti u PNKA, a potom PNKA može lako biti pretvoren u regularni izraz uzastopnim kolabriranjem dijelova u jedinstvene bridove (grane) sve dok nije zadovoljeno S = {s, a}. Na sličan se način PNKA može reducirati na NKA promjenom operatora regularnih izraza u nove bridove, sve dok svaki brid nije označen regularnim izrazom koji prihvaća jedinstven niz znakova duljine najviše 1. S druge strane, svaki NKA može biti reduciran na NKA koristeći tehniku konstrukcije partitivnog skupa, u kojoj su pojedini elementi skupa svih podskupova elementi novog skupa. Iz ovoga slijedi da PNKA prepoznaju isti skup formalnih jezika kao i DKAi te NKAi.