Autômato finito alternado

Predefinição:Sem-fontes 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(\mathrm{\exists }),S(\mathrm{\forall }),\mathrm{\Sigma },\delta ,P_0,F)$, onde

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