Please enable JavaScript.
Coggle requires JavaScript to display documents.
AUTOMATAS - Coggle Diagram
AUTOMATAS
? = una función de transición
qf = un conjunto de estados finales
q0 = un estado inicial
? = un conjunto finito de símbolos de entrada
Q = un conjunto finito de estados
El modelo matemático de un automata consta de cinco elementos que son:
DETERMINISTAS
La transición desde un estado puede tener como destino un único estado. Por eso se llama determinista.
No se aceptan transiciones con cadenas vacías.
Se permite el uso de backtracking
Requiere mas espacio.
Una cadena es aceptada si su transición es hacia un estado final.
NO DETERMINISTAS
La transición desde un estado puede tener multiples destinos. Por eso se le llama no determinista.
Permite transiciones con cadenas vacías.
No siempre se permite el uso de backtracking.
Requiere menos espacio.
Una cadena es aceptada si solo una de todas sus posibles transiciones son hacia un estado final.
CONSTRUCCION DE UN AUTOMATA
ESTADOS
Los estados del automata son representados por círculo. Los nombres de los estados están escritos dentro de esos círculos.
ESTADO INICIAL
Estado en el cual el automata inicia. El estado inicial tiene una flecha apuntando hacia el.
ESTADOS INTERMEDIOS
Todos los estados intermedios tienen al menos 2 flechas; una apuntando hacia el estado y otra apuntando hacia otro estado.
ESTADO FINAL
Si una cadena es parseada exitosamente, se espera que el automata quede en este estado. Se representa con un circulo doble. Puede tener una cantidad impar de flechas apuntando hacia el y una cantidad par de flechas apuntando hacia otros estados.
TRANSICION
La transición de un estado a otro ocurre cuando un símbolo deseado es encontrado en la cadena de entrada. Después de una transición, un automata se puede mover al siguiente estado, o quedarse en el mismo estado. El movimiento de un estado a otro es representado por una flecha dirigida, esta flecha apunta al estado de destino.