Autómatas Finitos
Qué es un autómata finito? ?
- Modelado gráfico de una máquina abstracta que permite representar una serie de acciones o eventos y de estados.
- Modelan sistemas discretos o abstracciones de la realidad.
- Poseen una forma de grafo dirigido
- Siempre existe un solo estado inicial, uno o más estados finales, y 0 o más estados intermedios.
- Al terminar de avaluar la palabra, se debe haber llegado a un estado final, para se considerada legal.
Cuál es la definición formal de autómata? ?
Definición formal de Autómata
Es una máquina M formada por 5 elementos
- es un alfabeto de entrada
- es un conjunto finito de estados
- es el estado inicial
- es un conjunto de estados finales o de aceptación
- es una relación de transición
Cuáles son los elementos de un autómata finito? ?
- Estados (representados por nodos): alguna situación en la que se permanece un cierto tiempo.
- Son los símbolos no terminales
- Transiciones o eventos: situaciones instantáneas que marcan un cambio de un estado a otro.
- Son los símbolos terminales
- Trayectoria: Camino recorrido por el autómata.
Cuál es el propósito de los autómatas? ?
- El propósito en estos modelos de estados y eventos, es el reconocer secuencias de acciones legales o inválidas
Qué tipos de autómatas finitos existen? ?
- Autómata finito determinista (AFD)
- Donde es una función de transición, es decir, que para cada par (estado actual y símbolo de entrada) le corresponde un único estado siguiente.
- Autómata finito no determinista (AFND)
- Donde no es necesariamente una función de transición
- Para cada par (estado actual y símbolo de entrada) le corresponde cero, uno dos o más estados siguientes. Normalmente la relación de transición se denota
- Donde no es necesariamente una función de transición
Cómo se relaciona una tabla de transición con una representación en grafo? ?