Un autómata es un modelo matemático que describe un sistema que puede estar en varios estados diferentes y cambiar entre ellos mediante transiciones controladas por un conjunto de entradas. Los autómatas son ampliamente utilizados en teoría de la computación para modelar sistemas formales, como lenguajes formales y máquinas de estado finito.
Existen varios tipos de autómatas, como el autómata finito(deterministas y no deterministas), el autómata de pila y el autómata de transición de estados. Cada tipo tiene sus propias características y aplicaciones específicas.
Los autómatas finitos son aquellos que tienen una cantidad limitada de estados y son deterministas porque en cada estado transporta una única variable (letra).
Ejemplos:
Deterministas → conecta Q0 con Q1 solo por a.
No deterministas → Conecta a Q0 con Q1 por a y por b.
Definir un autómata consta de nombrar el conjunto de estados (o conjunto de vértices), el alfabeto que transporta(pueden ser letras o números), el estado inicial (indicado por una flecha y siempre es uno solo), los estados finales o de aceptación(graficados con doble circulo) y la función de incidencia (relación entre estado y estado).
Notar que en la función de incidencia armamos una tabla donde tenemos la función y cada elemento del alfabeto es una columna; Vamos a marcar “a donde se puede llegar”, por ejemplo, en la fila de Q0 con a podemos llegar a Q1 y con b podemos llegar a Q2. En otros casos hay conjunto vacío cuando no es posible ese caso.
