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 ( q , a , q 1 ∨ q 2 ) {\displaystyle (q,a,q_{1}\vee q_{2})} , A nedeterministički odabire prijelaz trenutnog stanja u ili q 1 {\displaystyle q_{1}} ili q 2 {\displaystyle q_{2}} prilikom čitanja a. Za svaki prijelaz ( q , a , q 1 ∧ q 2 ) {\displaystyle (q,a,q_{1}\wedge q_{2})} , A prelazi u stanja q 1 {\displaystyle q_{1}} i q 2 {\displaystyle q_{2}} 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č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 2 k {\displaystyle 2^{k}} 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 { { q 1 } { q 2 , q 3 } } {\displaystyle \{\{q_{1}\}\{q_{2},q_{3}\}\}} predstavljalo q 1 ∨ ( q 2 ∧ q 3 ) {\displaystyle q_{1}\vee (q_{2}\wedge q_{3})} - stanje tt (istina) je predstavljeno sa { { } } {\displaystyle \{\{\}\}} u ovom slučaju, a stanje ff (laž) sa ∅ {\displaystyle \emptyset } . Predstavljanje u obliku formuli je obično učinkovitije.