Autômato finito alternado: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: A migrar 3 interwikis, agora providenciados por Wikidata em d:Q3300791 |
|||
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|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
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.
| |||