2615315
Autómatas Finitos
- 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.
- 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.
- ClasificaciÓn de AF
- Deterministas
- Cada combinación (estado,
símbolo de entrada) produce
un solo estado.
- 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 λ.
- Cada combinación (estado,
símbolo de entrada) produce
varios estados y además son
posibles las transiciones con λ.
- Deterministas
- 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
- 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.
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.