Definición

• Es una herramienta abstracta que se utiliza para reconocer un determinado LR.
• Es un modelo formal matemático de un sistema que recibe una cadena constituida por símbolos de cierto alfabeto Σ y tiene capacidad de determinar si esa cadena pertenece al LR que el AF reconoce.
• Es una máquina de estados finitos. Una máquina es una abstracción matemática que capturan solamente el aspecto referente a las secuencias de eventos (transiciones) que ocurren.

Reconocimiento

• RECONOCER un LR: aceptar cada cadena que es una palabra del LR y rechazar cada cadena que no pertenece al lenguaje.
• Una palabra es aceptada si:
  • Cadena ha sido consumida (se ha analizado todos los símbolos de la cadena)
  • El AF se encuentra en un estado especial llamado ESTADO FINAL o ESTADO DE ACEPTACIÓN.

Definición formal

• Formalmente un autómata finito se define como una 5-upla: M = <Q, Σ, q0, F, δ>
  • Q: conjunto finito de estados.
  • Σ: alfabeto (conjunto finito de símbolos) de entrada reconocido por el autómata.
  • q0: estado inicial q0 ∈ Q, único en un conjunto.
  • F: conjunto de estados finales o estados de aceptación, F ⊆ Q.
  • δ: función de transición de estados, δ: Q x Σ -> Q.

Representación gráfica

• Un autómata generalmente se representa por un grafo dirigido y etiquetado (etiquetas posibles: ó o λ), llamado diagrama de transición de estados.
• Cada nodo o vértice representa un estado.
• Cada flecha o arista representa una transición.
• El estado inicial se representa con un nodo con una flecha que no tiene origen.
• Los estado finales se representan por doble círculo.

Casos

• ACEPTACIÓN: cadena ab
  • ACTIVIDAD: q0 -> a -> q0 -> b -> q1 ACEPTA
  • Se dice que la cadena w es aceptada por el AF M cuando δ(q0, w) ∈ F
  • Se define el Lenguaje aceptado por el AF M como: L(M) = {w ∈ Σ* / δ(q0, w) ∈ F}
• RECHAZO: cadena a
  • ACTIVIDAD: q0 -> a -> q0 RECHAZA
• RECHAZO: cadena abab
  • ACTIVIDAD: q0 -> a -> q0 -> b -> q1 -> a -> ? RECHAZA