Mostrando entradas con la etiqueta deterministas. Mostrar todas las entradas
Mostrando entradas con la etiqueta deterministas. Mostrar todas las entradas

lunes, 4 de abril de 2016

3. Autómatas de Estados Finitos

Aplicación de los autómatas en los procesadores de lenguaje

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: