Diseño del compilador: autómatas finitos

Los autómatas finitos son una máquina de estado que toma una cadena de símbolos como entrada y cambia su estado en consecuencia. Los autómatas finitos son un reconocedor de expresiones regulares. Cuando una cadena de expresión regular se introduce en autómatas finitos, cambia su estado para cada literal. Si la cadena de entrada se procesa con éxito y el autómata alcanza su estado final, se acepta, es decir, se dice que la cadena recién introducida es una ficha válida del idioma en cuestión.

El modelo matemático de autómatas finitos consta de:

  • Conjunto finito de estados (Q)
  • Conjunto finito de símbolos de entrada (Σ)
  • Un estado de inicio (q0)
  • Conjunto de estados finales (qf)
  • Función de transición (δ)

La función de transición (δ) mapea el conjunto finito de estado (Q) a un conjunto finito de símbolos de entrada (Σ), Q × Σ ➔ Q

Construcción de autómatas finitos

Sea L (r) un lenguaje regular reconocido por algunos autómatas finitos (FA).

  • States: Los estados de FA están representados por círculos. Los nombres de los estados están escritos dentro de círculos.

  • Start state: El estado desde donde comienza el autómata se conoce como estado de inicio. El estado de inicio tiene una flecha apuntando hacia él.

  • Intermediate states: Todos los estados intermedios tienen al menos dos flechas; uno apuntando hacia ellos y otro apuntando hacia ellos.

  • Final state: Si la cadena de entrada se analiza correctamente, se espera que los autómatas estén en este estado. El estado final está representado por círculos dobles. Puede tener cualquier número impar de flechas apuntando hacia él y un número par de flechas apuntando hacia él. El número de flechas impares es uno mayor que par, es decirodd = even+1.

  • Transition: La transición de un estado a otro ocurre cuando se encuentra un símbolo deseado en la entrada. Tras la transición, los autómatas pueden pasar al siguiente estado o permanecer en el mismo estado. El movimiento de un estado a otro se muestra como una flecha dirigida, donde las flechas apuntan al estado de destino. Si los autómatas permanecen en el mismo estado, se dibuja una flecha que apunta de un estado a sí mismo.

Example: Suponemos que FA acepta cualquier valor binario de tres dígitos que termine en el dígito 1. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}