title: Alternerende eindige automaat
text: In de theoretische informatica is een alternerende eindige automaat een variant op een eindige automaat. Een toestand van een eindige automaat accepteert een woord , waarbij  een symbool van het alfabet is en  de rest van het woord, wanneer minstens een van zijn -opvolgertoestanden de  accepteert. Een alternerende eindige automaat past echter een willekeurige booleaanse functie op de acceptatiewaardes van zijn opvolgertoestanden toe.
  
  De naam baseert zich op het volgende: Als we lege overgangen toestaan (wat in het geval van eindige automaten niet gebruikelijk is), hebben we slechts twee soorten toestanden nodig om alle mogelijke booleaanse functies te kunnen uitdrukken: toestanden die  accepteren als alle opvolgertoestanden  accepteren, en toestanden die  accepteren als minstens één opvolgertoestand  accepteert. De automaat alterneert dan als het ware tussen "alle"- en "één"-toestanden.
  
  Formele definitie 
  
  Een alternerende eindige automaat is een tupel  waarbij
    een eindige verzameling toestanden is;
    het eindige invoeralfabet;
    de begintoestand;
    de verzameling eindtoestanden; en
    de transitiefunctie.
   staat hier voor de verzameling van waarheidswaarden. De transitiefunctie  kent aan elke toestand  een functie  toe, die gegeven een alfabetsymbool en een waarheidswaarde voor elke toestand, een waarheidswaarde teruggeeft.
  
  Om makkelijk functies van toestanden naar waarheidswaarden op te kunnen schrijven, worden de toestanden geordend. We kunnen een functie van toestanden naar waarheidswaarden nu als tupels opschrijven. Als , dan wordt met  de functie met ,  en  bedoeld. De functie  is de karakteristieke functie van de verzameling eindtoestanden, dat wil zeggen:
  
  We definiëren nu de functie  als de uitbreiding van de transitiefunctie  van symbolen naar woorden:
   
   
  en definiëren de taal van een automaat , dat wil zeggen, de verzameling van woorden die door  geaccepteerd worden, als:
   .
  
  Voorbeeld 
  
  De volgende alternerende eindige automaat over het alfabet  zij gegeven:
   , waarbij
   
   
  De automaat  accepteert de volgende taal:
   
  Deze alternerende eindige automaat heeft 1 toestand. De kleinste niet-deterministische eindige automaat die dezelfde taal accepteert heeft 2 toestanden; de kleinste deterministische eindige automaat zelfs 4.
  
  Eigenschappen 
  
  Niet-deterministische eindige automaten (NFAs) zijn een speciaal geval van alternerende automaten; voor elke reguliere taal bestaat dus een alternerende eindige automaat die de taal accepteert. Andersom is ook het geval: elke alternerende eindige automaat kan in een equivalente NFA worden omgevormd. De alternerende eindige automaten accepteren dus precies de klasse der reguliere talen. Alternerende eindige automaten kunnen echter veel kleiner zijn dan equivalente eindige automaten. Voor elke  bestaat er een alternerende eindige automaat met  toestanden, waarvoor geldt dat de kleinste equivalente NFA  en de kleinste equivalente deterministische eindige automaat (DFA) zelfs  toestanden heeft (zie het voorbeeld hierboven).
  
  Literatuur 
  
   Ashok K. Chandra, Dexter C. Kozen and Larry J. Stockmeyer. Alternation. Journal of the Association for Computing Machinery, 28(1), 1981.
  
  Theoretische informatica