Generalizirani nedeterministički konačni automat

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web-stranice ili drugi izvori).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.

U teoriji računanja, generalizirani nedeterministički konačni automat (GNKA) 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[uredi | uredi izvor]

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 (sS)
  • prihvatljivo stanje (aS)

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.