automatas finitos

Teoría de Autómatas I
Autómatas finitos y lenguajes regulares

-1-

AUTÓMATAS FINITOS Y
LENGUAJES REGULARES
- Autómatas finitos: reconocen lenguajes regulares.
- Aplicación más importante: construcción de compiladores (analizadores léxicos).
ANÁLISIS LÉXICO
- Token: elemento del lenguaje (palabra reservada, nombre de variable, punto y coma,
constante, etc).
- Marcas de fin de cadena:delimitan los tokens.
Diagrama de transición de estados
- Colección finita de círculos conectados por arcos.
• Círculos: estados.
∗ Estado inicial: marcado con un puntero.
∗ Estados finales o de aceptación: marcados por círculos dobles.
∗ Estados “intermedios”.
• Arcos dirigidos: transiciones.
∗ Etiquetados con símbolos o categorías de símbolos.
∗ Se transita de un estado a otro trasrecibir a la entrada el símbolo de la
etiqueta.
- Ejemplo:

Teoría de Autómatas I
Autómatas finitos y lenguajes regulares

-2-

- Proceso de reconocimiento de una cadena:
• Se parte del estado inicial (actual).
• Se lee la cadena símbolo a símbolo de izquierda a derecha.
• Por cada símbolo leído se produce una transición desde el estado actual a otro
a través de la flecha cuya etiquetacoincide con el símbolo leído.
• La cadena es reconocida si tras realizar las transiciones correspondientes a la
cadena completa se alcanza un estado de aceptación.
- Ejemplos:
Cadena de entrada: i24
Transiciones: 1  i → 3  2 → 3  4 → 3 : cadena acept



ada
Cadena de entrada: 18
Transiciones: 1  1 → 2  8 → 2 : cadena r
echazada


Tabla de transición de estados
- Matrizbidimensional cuyos elementos proporcionan el resumen de un diagrama de
transiciones.
• Tantas filas como estados.
• Tantas columnas como símbolos de entrada.
• Columna adicional etiquetada con FDC para marcar los estados de
aceptación.
- Conversión de diagrama de transición a tabla de transición:
• Si del estado i se pasa al estado j a través de un arco de etiqueta n, rellenar la
casilla(i,n) con j.
• Si no existe ninguna transición desde el estado i con el símbolo n, marcar la
casilla correspondiente con un estado de error.
- Ejemplo:

1
2
3

letra
3
error
3

dígito
2
error
3

FDC
error
error
aceptar

Teoría de Autómatas I
Autómatas finitos y lenguajes regulares

-3-

AUTÓMATAS FINITOS DETERMINISTAS (AFD)
- Definiciones:
• Alfabeto: conjunto finitode símbolos.
• Cadena: secuencia de símbolos de un alfabeto terminada por un símbolo de
fin de cadena.
• Flujo de entrada a un autómata: cadenas analizadas.
- AFD: máquina conceptual.
• Flujo de entrada: cinta de entrada con símbolos grabados.
• Proceso de reconocimiento:
∗ Cabeza lectora que avanza en un único sentido.
∗ Mecanismo de control de transiciones.
- Mecanismo de control en unAFD:
• Gobierna las transiciones de estado de la máquina en función del flujo de
entrada.
• Se representa por un diagrama de transición o una tabla de transición.
- AFD: máquina analizadora de cadenas que acepta las cadenas aceptadas por su
diagrama de transición, y rechaza las restantes.
• Finito: tiene un número finito de estados.
• Determinista: siempre existe una y sólo una transiciónposible.
- AFD: M(S,Σ,δ,i,F)
• S: conjunto finito de estados.
• Σ: alfabeto de entrada.
• δ: función de transición de estados: S x Σ → S.
• i: estado inicial.
• F: conjunto de estados de aceptación: F ⊆ S
- δ( x) = q ⇔ p  x → q

p,
- Proceso de reconocimiento:
x1x2 .. n ∈ L( ) ⇔ ∃ s0s1s2..sn
.x
M
.

x1
x2
xn
i= s0 → s1  → s2 ..  → sn ∈ F ∧
.

∧ ∀j 0 ≤ j≤ n δ( j, j)=sj+1
s x
- Cadena vacía (λ): aceptada por el AFD si y sólo si i ∈ F.
- Diagrama de transición determinista:
• El diagrama está completamente definido: de cada estado sale un arco y sólo
uno con cada símbolo del alfabeto.
• Si el diagrama es no determinista, añadir un estado de rechazo de captación
global.

Teoría de Autómatas I
Autómatas finitos y lenguajes regulares

-4-

LÍMITES...