Generalizirani nedeterministički konačni automat
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
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.
GNKA se može definisati kao uređena petorka (S, Σ, T, s, a), koju čine:
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.