From Wikipedia, the free encyclopedia
U teoriji automata, alternirajući konačni automat (AKA) je nedeterministički konačni automat čije prijelaze dijelimo na egzistencijalne i univerzalne. Neka je A alternirajući automat:
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
Uočite da zbog univerzalne kvantifikacije je slijed prijelaza predstavljen stablom izvođenja (engl. run tree). A prihvata riječ w ako postoji stablo nad w takvo da svaki put stabla završava u prihvatljivom stanju.
Osnovni teorem kaže da je svaki AKA istovjetan nedeterminističkom konačnom automatu (NKA) obavljanjem slične konstrukcije partitivnog skupa kao što se koristi prilikom konverzije NKA u deterministički konačni automat (DKA). Ova tehnika konstrukcije konvertira AKA sa k stanja u NKA sa najviše stanja.
Alternativni često korišteni model jest onaj u kojem su logičke (Booleove) kombinacije predstavljene kao formule logike sudova. Na primjer, pretpostavljajući da su kombinacije u disjunktivnoj normalnoj formi, pri čemu bi predstavljalo - stanje tt (istina) je predstavljeno sa u ovom slučaju, a stanje ff (laž) sa . Predstavljanje u obliku formuli je obično učinkovitije.
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.