Алтернирајући коначни аутомат

У теорији аутомата, алтернирајући коначни аутомат (АКА), јесте недетерминистички коначни аутомат чији се прелази деле на егзистенцијалне и универзалне. Ако је А алтернирајући аутомат:

• за сваки прелаз $(q,a,q_{1}\vee q_{2})$, А недетерминистички одабире прелаз тренутног стања у или $q_{1}$ или $q_{2}$ приликом читања а;
• за сваки прелаз $(q,a,q_{1}\wedge q_{2})$, А прелази у стања $q_{1}$ и $q_{2}$ приликом читања ’а’.

Могуће је да се уочи да је због универзалне квантификације след прелаза представљен тзв. стаблом извођења (енгл. run tree). А прихвата w ако „постоји” стабло над w такво да баш сваки пут стабло завршава у прихватљивом стању.

Основна теорема има садржај да је сваки АКА истоветан недетерминистичком коначном аутомату (НКА) обављањем сличне конструкције партитивног скупа — као што се користи приликом конверзије НКА у детерминистички коначни аутомат (ДКА). Ова техника конструкције конвертује АКА са k стања у НКА, и то са највише $2^{k}$ стања.

Алтернативни често коришћен модел јест онај у којем су логичке (булеанске) комбинације представљене као формуле логике судова. На пример, претпостављајући да су комбинације у дисјунктивној нормалној форми, при чему би $\{\{q_{1}\}\{q_{2},q_{3}\}\}$ представљало $q_{1}\vee (q_{2}\wedge q_{3})$ тј. стање tt (тзв. истина) које је представљено овако: $\{\{\}\}$ (у овом случају), док је стање ff (тзв. лаж) представљено овако: $\emptyset$. Представљање у облику формула обично је учинковитије.