Autômato finito alternado

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes. (desde dezembro de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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 boleanas 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[editar | editar código-fonte]

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).