Teoria da computação – AFD e AFN
Saudações galera, estamos aqui mais uma vez para passarmos um pouco de teoria da computação para vocês! Caso sintam alguma duvida ou não sabe, veja os poster anteriores sobre “teoria da computação“.
O que é AFD – Autômato Finito Determinístico
Exatamente uma trajetória sobre uma cadeia w∈ Σ*
Exemplo de um AFD. Lembrando que AFD e uma 5-upla.
O que é AFN – Autômato Finito não Determinístico
Nenhuma, uma ou varias trajetórias sobre uma cadeia w∈ Σ*
Exemplo de uma AFN. Lembrando que AFN também é uma 5-upla.
Autômatos não determinísticos são uma generalização de autômatos determinísticos. Todo autômato determinístico é, por definição, não determinístico. O contrário não é verdade.
Autômato A aceita palavra w se existe uma trajetória de A sobre w que termina num estado de aceitação.
Ex.:
Aceita: ε, a, baba, baa, aaa;
Não aceita : b, bb, babba, baab.
Duvidas sobre 5-tupla?
Lembrando que AFN também é uma 5-upla.
Equivalência entre AFNs e AFDs
- AFNs e AFDs reconhecem a mesma classe de linguagens
- Duas máquinas são equivalentes se elas reconhecem a mesma linguagem.
- Todo AFN tem um AFD equivalente.
Próximo poster será sobre conversão, duvidas? Vejam postagem anteriores!
