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 ${\displaystyle (q,a,q_{1}\vee q_{2})}$, A escolhe não-deterministicamente mudar o estado para ${\displaystyle q_{1}}$ ou ${\displaystyle q_{2}}$, lendo a. Comportando-se, assim, como um autômato finito não-determinístico regular.
• Para uma transição universal ${\displaystyle (q,a,q_{1}\wedge q_{2})}$, A move para ${\displaystyle q_{1}}$ e ${\displaystyle 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é ${\displaystyle 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 ${\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}$ poderia representar ${\displaystyle q_{1}\vee (q_{2}\wedge q_{3})}$. O estado tt (true) é representado por ${\displaystyle \{\{\}\}}$ nesse caso e ff (false) por ${\displaystyle \varnothing }$. Essa representação de cláusulas é normalmente mais eficiente.

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

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