Alternirajući konačni automat

Из Википедије, слободне енциклопедије

U teoriji automata, alternirajući konačni automat (AKA) je nedeterministički konačni automat čiji se prelazi dele na egzistencijalne i univerzalne[obrazložiti]. Neka je A alternirajući automat:

  • Za svaki prelaz (q, a, q_1 \vee q_2), A nedeterministički odabira 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.

Uočite da zbog univerzalne kvantifikacije je sled prelaza predstavljen stablom izvođenja (engl. run tree). A prihvata reč w ako postoji stablo nad w takvo da svaki put stabla završava u prihvatljivom stanju.

Osnovna teorema kaže 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 sa najviše 2^k stanja.

Alternativni često korišćeni model jeste onaj u kojem su logičke (Booleove) 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) - stanje tt (istina) je predstavljeno sa \{\{\}\} u ovom slučaju, a stanje ff (laž) sa \emptyset. Predstavljanje u obliku formuli je obično učinkovitije.