Autômato finito alternado

Na teoria dos autômatos, um autômato finito alternado (AFA) é um autômato finito não-determinístico cujas transições são dividas em transições existenciais e universais. Por exemplo, consideremos A como um autômato alternado.

• Para uma transição existencial $(q,a,q_{1}\vee q_{2})$, A escolhe não-deterministicamente mudar o estado para $q_{1}$ ou $q_{2}$, lendo a. Comportando-se, assim, como um autômato finito não-determinístico regular.
• Para uma transição universal $(q,a,q_{1}\wedge q_{2})$, A move para $q_{1}$ e $q_{2}$, lendo a, simulando o comportamento de uma máquina paralela.

Por causa do quantificador universal uma execução é representada por uma árvore de execuções. A aceita uma palavra w, se existe uma árvore de execução sobre w na qual todo caminho termina em um estado de aceitação.

Um teorema básico diz que qualquer AFA é equivalente a um autômato finito não determinístico (AFN), executando um tipo similar de construção tão poderosa como a que é usada na transformação de um AFN para um autômato finito determinístico (AFD). Essa construção converte um AFA com k estados para um AFN que possui até $2^{k}$ estados.

Um modelo alternativo que é frequentemente usado é aquele em que combinações de booleanas são representados como cláusulas. Por exemplo, pode-se assumir as combinações para estar na Forma Normal Disjuntiva então $\{\{q_{1}\},\{q_{2},q_{3}\}\}$ poderia representar $q_{1}\vee (q_{2}\wedge q_{3})$. O estado tt (true) é representado por $\{\{\}\}$ nesse caso e ff (false) por $\varnothing$. Essa representação de cláusulas é normalmente mais eficiente.

Definição Formal

Um autômato finito alternado (AFA) é uma 6-tupla, $(S(\exists ),S(\forall ),\Sigma ,\delta ,P_{0},F)$, onde

• $S(\exists )$ é um conjunto finito de estados existenciais. Comumente representado como $S(\vee )$.
• $S(\forall )$ é um conjunto finito de estados universais. Comumente representado como $S(\wedge )$.
• $\ \Sigma$ é um conjunto finito de símbolos de entrada.
• $\ \delta$ é um conjunto de funções de transição para o próximo estado $(S(\exists )\cup S(\forall ))\times (\Sigma \cup \{\varepsilon \})\to 2^{S(\exists )\cup S(\forall )}$.
• $\ P_{0}$ é o estado inicial, tal que $P_{0}\in S(\exists )\cup S(\forall )$.
• $\ F$ é o conjunto dos estados de aceitação, tal que $F\subseteq S(\exists )\cup S(\forall )$.