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
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.