Resumen: Semana del 28 de marzo al 3 de abril

(1/8)

Autómatas finitos

• Para entender el funcionamiento de lex (y del análisis léxico), así como muchas otras cosas del curso, se debe recurrir a los autómatas finitos
• Un autómata finito es un grafo que reconoce expresiones regulares, aprobándolas o rechazándolas en relación con cada posible cadena de entrada

(2/8)

Diagramas de transición

• Los autómatas finitos a menudo se representan mediante un diagrama de transición
• Un diagrama de transición de estados sirve para indicar el flujo de caracteres que deben ocurrir para encontrar lexema(s)
• Un diagrama de transición se compone de los siguientes elementos:
  • Un punto inicial (representado por un círculo numerado)
  • Una serie de puntos (representados también por círculos numerados)
  • Un conjunto de flechas que conectan los puntos, e indican qué entrada se requiere para avanzar a través de ellas
  • Uno o más puntos finales (círculos dobles numerados) donde termina la entrada

(3/8)

Autómatas finitos no deterministas

• Los autómatas finitos pueden ser deterministas o no deterministas, donde los deterministas son más estrictos
• Un autómata finito no determinista (AFN) consiste en:
  • Un número finito de estados
    • De estos, uno es considerado el estado inicial
    • Un subconjunto más es considerado como el conjunto de estados aceptantes o finales
  • Un conjunto de símbolos de entrada, alias el alfabeto de entrada
    • Opcionalmente, un símbolo épsilon (ϵ) que representa la cadena vacía y no forma parte del alfabeto de entrada, pero deja pasar sin ocupar caracter
  • Una función de transición que para cada estado y cada símbolo de entrada permita una transición al estado siguiente

(4/8)

Autómatas finitos no deterministas: Un diagrama de ejemplo

• En este caso, el autómata tiene como alfabeto de entrada las letras a y b
• El autómata acepta caracteres a y b hasta encontrar una secuencia que dé exactamente la hilera "abb"

(5/8)

Autómatas finitos no deterministas: Un diagrama más complejo

(vilmente copipegado de la página del prof. Di Mare, espero no le importe...)

• Este otro diagrama hace exactamente lo mismo que el anterior, aunque un poco más complicadamente, pero es para ilustrar el concepto de épsilon
• En este caso hay un total de diez estados:
  • Los del 1 al 6 cubren el caso de encontrar cualquier cantidad de a's y/o de b's
  • Los del 7 al 9 cubren el caso de encontrar una secuencia "aab"
  • El 0 es el caso inicial, por lo que puede ir al 1 o directo al 7
  • El 10 es el caso final

(6/8)

Autómatas finitos no deterministas: Tablas de transición

• Las tablas de transición son otro método para mostrar un autómata finito
• Una tabla de transición tiene como filas a los estados, como columnas a los símbolos del alfabeto (más el épsilon), y en cada cruce los estados a los que se puede ir desde ese estado usando ese símbolo del alfabeto
• Por ejemplo, aquí está el esquema anterior como una tabla de transición

(7/8)

Autómatas finitos deterministas

• Un autómata finito determinista (AFD) es un AFN que:
  • No tiene movimientos épsilon
  • Para cada estado, cada uno de los símbolos del alfabeto conduce a exactamente un estado
• Los AFD son un avance sobre los AFN ya que son más compactos y menos propensos a ambigüedad

(8/8)

Autómatas finitos deterministas: un ejemplo

• Este ejemplo es el anterior ejemplo de AFN convertido a AFD
• Como se puede ver, no hay movimientos épsilon ni símbolos que conduzcan a múltiples estados
• La conversión de autómatas finitos no deterministas en deterministas se verá próximamente