U teoriji automata, alternirajući konačni automat (AKA), jeste nedeterministički konačni automat čiji se prelazi dele na egzistencijalne i univerzalne. Ako je A alternirajući automat: za svaki prelaz , A nedeterministički odabire prelaz trenutnog stanja u ili ili prilikom čitanja a; za svaki prelaz , A prelazi u stanja i prilikom čitanja ’a’.
Moguće je da se uoči da je zbog univerzalne kvantifikacije sled prelaza predstavljen tzv. stablom izvođenja (). A prihvata w ako „postoji” stablo nad w takvo da baš svaki put stablo završava u prihvatljivom stanju.
Osnovna teorema ima sadržaj da je svaki AKA istovetan 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 konvertuje AKA sa -{k}- stanja u NKA, i to sa najviše stanja.
Alternativni često korišćen model jest onaj u kojem su logičke (buleanske) kombinacije predstavljene kao formule logike sudova. Na primer, pretpostavljajući da su kombinacije u disjunktivnoj normalnoj formi, pri čemu bi predstavljalo tj. stanje -{tt}- (tzv. istina) koje je predstavljeno ovako: (u ovom slučaju), dok je stanje -{ff}- (tzv. laž) predstavljeno ovako: . Predstavljanje u obliku formula obično je učinkovitije.
Категорија:Аутомати