Alternirajući konačni automat

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:

• Za svaki prijelaz [math]\displaystyle{ (q, a, q_1 \vee q_2) }[/math], A nedeterministički odabire prijelaz trenutnog stanja u ili [math]\displaystyle{ q_1 }[/math] ili [math]\displaystyle{ q_2 }[/math] prilikom čitanja a.
• Za svaki prijelaz [math]\displaystyle{ (q, a, q_1 \wedge q_2) }[/math], A prelazi u stanja [math]\displaystyle{ q_1 }[/math] i [math]\displaystyle{ q_2 }[/math] prilikom čitanja a.

Uočite da zbog univerzalne kvantifikacije je slijed prijelaza predstavljen stablom izvođenja (engl. run tree). A prihvaća 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 [math]\displaystyle{ 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]\displaystyle{ \{\{q_1\}\{q_2,q_3\}\} }[/math] predstavljalo [math]\displaystyle{ q_1 \vee (q_2 \wedge q_3) }[/math] - stanje tt (istina) je predstavljeno sa [math]\displaystyle{ \{\{\}\} }[/math] u ovom slučaju, a stanje ff (laž) sa [math]\displaystyle{ \emptyset }[/math]. Predstavljanje u obliku formuli je obično učinkovitije.