Alternerende eindige automaat
Uit Wikipedia, de vrije encyclopedia
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.