Alternerende eindige automaat

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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 één 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[bewerken]

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[bewerken]

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[bewerken]

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[bewerken]

  • Ashok K. Chandra, Dexter C. Kozen and Larry J. Stockmeyer. Alternation. Journal of the Association for Computing Machinery, 28(1), 1981.