Generalizirani nedeterministički konačni automat

U teoriji računanja, generalizirani nedeterministički konačni automat (GNKA)^[1] je NKA u kojem svaki prijelaz može biti označen regularnim izrazom. GNKA čita blokove znakova (simbola) sa ulaza koji sačinjavaju niz znakova (string) kao što definiše regularni izraz nad prijelazom.

Formalna definicija

GNKA se može definisati 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 GNKA, a potom GNKA može lahko 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 GNKA može reducirati na NKA promjenom operatora regularnih izraza u nove bridove, sve dok svaki brid nije označen regularnim izrazom koji prihvata jedinstven niz znakova dužine 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.

Reference

1. "GNFA-Formal-Definition.pdf" (PDF).

Vanjski linkovi