Alternirajući konačni automat

Шаблон:Bez izvora-lat U teoriji automata, alternirajući konačni automat (AKA), jeste nedeterministički konačni automat čiji se prelazi dele na egzistencijalne i univerzalne.Шаблон:Pojasniti-lat 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 (Шаблон:Jez-engl). 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: $\mathrm{\varnothing }$. Predstavljanje u obliku formula obično je učinkovitije.