Izvorni kôd stranice Alternirajući konačni automat

{{Nedostaju izvori}}
U [[teorija automata|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 [[konačni automat|automat]]:

* Za svaki prijelaz <math>(q, a, q_1 \vee q_2)</math>, ''A'' nedeterministički odabire prijelaz trenutnog stanja u ili <math>q_1</math> ili <math>q_2</math> prilikom čitanja ''a''.
* Za svaki prijelaz <math>(q, a, q_1 \wedge q_2)</math>, ''A'' prelazi u stanja <math>q_1</math> ''i'' <math>q_2</math> prilikom čitanja ''a''.

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čki konačni automat|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 <math>2^k</math> 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 <math>\{\{q_1\}\{q_2,q_3\}\}</math> predstavljalo <math>q_1 \vee (q_2 \wedge q_3)</math> - stanje '''tt''' (''istina'') je predstavljeno sa <math>\{\{\}\}</math> u ovom slučaju, a stanje '''ff''' (''laž'') sa <math>\emptyset</math>.
Predstavljanje u obliku formuli je obično učinkovitije.

== Reference ==
{{Refspisak}}

== Vanjski linkovi ==
{{Normativna kontrola}}

[[Kategorija:Teorija automata]]