Autómatas Finitos

Autómatas Finitos

1. Definición Formal

   • Al describir un autómata de estados finitos, debemos escribir la información que varia de un autómata a otro, porque no tiene sentido describir características que comparte con otros. Esto son las que aparecen en los diagramas de estados y transiciones.

2. ClasificaciÓn de AF

   • Deterministas
     • Cada combinación (estado, símbolo de entrada) produce un solo estado.
   • No Deterministas
     • Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

3. Conversión de un AFND a AFD

   • Todo AFND puede convertirse en un AFD equivalente, que mantiene el alfabeto Σ y el estado inicial q0 originales. La conversión implica pasar por un AFD intermedio con estados y transiciones redundantes, que al no ser accesibles a partir del estado inicial, son eliminados para obtener el AFD definitivo.
   • Ejemplo

Imagens e arquivos do mapa