Automatas

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 tras recibir a la entradael 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 etiqueta coincide con el símbololeí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 - Matriz bidimensional cuyos elementosproporcionan 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óndesde el estado i con el símbolo n, marcar la casilla correspondiente con un estado de error. - Ejemplo: letra 3 error 3 dígito 2 error 3 FDC error error aceptar

1 2 3

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

-3-

AUTÓMATAS FINITOS DETERMINISTAS (AFD) - Definiciones: • Alfabeto: conjunto finito de símbolos. • Cadena: secuencia de símbolos de un alfabeto terminada porun 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 un AFD: • Gobierna las transiciones de estado de la máquina en función del flujo deentrada. • 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ón posible. - 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 DE LOS AUTÓMATAS FINITOS DETERMINISTAS - Longitud de una cadena w: w - Σ*: conjunto de cadenas de longitud finita...