Alternirajući konačni automat

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 $(q,a,q_{1}\vee q_{2})$, A nedeterministički odabire prelaz trenutnog stanja u ili $q_{1}$ ili $q_{2}$ prilikom čitanja a;
• za svaki prelaz $(q,a,q_{1}\wedge q_{2})$, A prelazi u stanja $q_{1}$ i $q_{2}$ prilikom čitanja ’a’.

Moguće je da se uoči da je zbog univerzalne kvantifikacije sled prelaza predstavljen tzv. stablom izvođenja (engl. run tree). 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 $2^{k}$ 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 $\{\{q_{1}\}\{q_{2},q_{3}\}\}$ predstavljalo $q_{1}\vee (q_{2}\wedge q_{3})$ tj. stanje tt (tzv. istina) koje je predstavljeno ovako: $\{\{\}\}$ (u ovom slučaju), dok je stanje ff (tzv. laž) predstavljeno ovako: $\emptyset$. Predstavljanje u obliku formula obično je učinkovitije.