La tarea de comprobar si una sentencia pertenece o no a un determinado lenguaje se encomienda a los autómatas. En el campo de estudio de los traductores, compiladores, procesadores e intérpretes los autómatas se utilizan como reconocedores de lenguajes, que dada una cadena de símbolos indican si dicha cadena pertenece o no al lenguaje.
Una cadena pertenece a un lenguaje si el autómata reconocedor de dicho lenguaje lo toma como entrada, y partiendo del estado inicial transita a través de varias configuraciones hasta que alcanza el estado final.
Autómatas finitos
Un autómata finito es un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un alfabeto. Un diagrama de transición es un autómata finito.
Existen dos tipos autómatas finitos, los cuales son:
- Autómatas finitos deterministas (AFD)
- Autómatas finitos no deterministas (AFND)
Autómatas finitos deterministas (AFD)
Definición. Una máquina de estados finitos M es un quíntuplo (K, Σ, δ, s, F), donde: