Autômato finito alternado: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado

Em linha

Edição atual tal como às 01h20min de 21 de maio de 2015

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

@@ Linha 7: / Linha 7: @@
 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é <math>2^k</math> estados.
+Um teorema básico diz que qualquer AFA é equivalente a um [[autômato finito não-determinístico|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é <math>2^k</math> estados.
-Um modelo alternativo que é frequentemente usado é aquele em que combinações de boleanas são representados como ''cláusulas''.
+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|Forma Normal Disjuntiva]] então <math>\{\{q_1\},\{q_2,q_3\}\}</math> poderia representar  <math>q_1 \vee (q_2 \wedge q_3)</math>. O estado '''tt''' (''true'') é representado por <math>\{\{\}\}</math> nesse caso e '''ff''' (''false'') por <math>\varnothing</math>. Essa representação de cláusulas é normalmente mais eficiente.