Compiladores

Autómata finito: Es un vector que tiene un conjunto de entradas finitas denominadas con la letra i un conjuntos finito de estados (no vacíos) un delta denominado función de transición y un conjunto universal de todos los estados.

Existen dos tipos autómatas finitos, los cuales son:

Autómata finito determinista: es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.



Autómata finito no determinista: Una extensión de los AFD’S es la de permitir que de cada estado o nodo del diagrama de estados salga un número de flechas mayor o menor que |Σ|. Así se puede permitir que falte la flecha correspondiente a alguno de los símbolos del alfabeto, o bien que haya varias flechas que salgan de un solo nodo con la misma etiqueta. Inclusive se permite que las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacía.

Definición. Un autómata finito no determinista es un quíntuplo (K, Σ, Δ, s, F), donde K, Σ, s y F tienen el mismo significado para el caso de los AFD y Δ, llamada la relación de transición, es un subconjunto finito K X Σ* X K.