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 $w=ax$, waarbij $a$ een symbool van het alfabet is en $x$ de rest van het woord, wanneer minstens een van zijn $a$-opvolgertoestanden de $x$ 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 $ax$ accepteren als alle opvolgertoestanden $x$ accepteren, en toestanden die $ax$ accepteren als minstens één opvolgertoestand $x$ accepteert. De automaat alterneert dan als het ware tussen "alle"- en "één"-toestanden.

Formele definitie

Een alternerende eindige automaat is een tupel $𝒜=(Q,\mathrm{\Sigma },q_1,F,g)$ waarbij

• $Q=\{q_1,\dots ,q_k\}$ een eindige verzameling toestanden is;
• $\mathrm{\Sigma }$ het eindige invoeralfabet;
• $q_1\in Q$ de begintoestand;
• $F\subseteq Q$ de verzameling eindtoestanden; en
• $g:Q\to (\mathrm{\Sigma }\to {𝔹}^k\to 𝔹)$ de transitiefunctie.

$𝔹=\{0,1\}$ staat hier voor de verzameling van waarheidswaarden. De transitiefunctie $g$ kent aan elke toestand $q$ een functie $g(q):\mathrm{\Sigma }\times {𝔹}^k\to 𝔹$ 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 $Q=\{q_1,q_2,q_3\}$, dan wordt met $𝐮=(1,0,0)$ de functie met $𝐮(q_1)=1$, $𝐮(q_2)=0$ en $𝐮(q_3)=0$ bedoeld. De functie $𝐟$ is de karakteristieke functie van de verzameling eindtoestanden, dat wil zeggen:

$𝐟(q)=\{\begin{array}{cc}1& \text{als }q\in F\\ 0& \text{als }q\notin F\end{array}$

We definiëren nu de functie $H:Q\to ({\mathrm{\Sigma }}^{*}\to {𝔹}^k\to 𝔹)$ als de uitbreiding van de transitiefunctie $g$ van symbolen naar woorden:

$H(q)(ϵ)(𝐮)=𝐮(q)$

$H(q)(ax)(𝐮)=g(q)(a)(H(q_1)(x),\dots ,H(q_k)(x))$

en definiëren de taal van een automaat $𝒜$, dat wil zeggen, de verzameling van woorden die door $𝒜$ geaccepteerd worden, als:

$L(𝒜)=\{w\mid H(q_1)(w)(𝐟)=1\}$.

Voorbeeld

De volgende alternerende eindige automaat over het alfabet $\mathrm{\Sigma }=\{a,b\}$ zij gegeven:

$𝒜=(\{q_1\},\mathrm{\Sigma },q_1,\{q_1\},g)$, waarbij

$g(q_1)(a)(x)=\mathrm{\neg }x$

$g(q_1)(b)(x)=0$

De automaat $𝒜$ accepteert de volgende taal:

$L(𝒜)=\{a^{2n}\mid n\in \mathbb{N}\}\cup \{a^{2n+1}bw\mid n\in \mathbb{N},w\in {\mathrm{\Sigma }}^{*}\}$

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 $k\in \mathbb{N}$ bestaat er een alternerende eindige automaat met $k$ toestanden, waarvoor geldt dat de kleinste equivalente NFA $2^k$ en de kleinste equivalente deterministische eindige automaat (DFA) zelfs $2^{2^k}$ 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.