Alternerende eindige automaat
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
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 heefttoestand . De kleinste niet-deterministische eindige automaat die dezelfde taal accepteert heefttoestanden ; de kleinste deterministische eindige automaat zelfs 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,1 ) , Theoretische informatica