Máquinas de Estado Finito y Autómatas: Conceptos Fundamentales

Fundamentos de Máquinas de Estado Finito y Autómatas

1. Definición de Máquina de Estado Finito (MEF)

Una Máquina de Estado Finito (MEF) M es una 5-tupla M = (Q, Σ, δ, q₀, F) tal que:

• Q = {q₀, q₁, ..., qₘ} es un conjunto finito de estados de la máquina.
• Σ = {e₁, e₂, ..., eₙ} es un conjunto finito de símbolos de entrada (el alfabeto).
• δ: Q × Σ → Q es la función de transición de estados (para Autómatas Finitos Deterministas - AFD). Asocia un estado siguiente a cada par de estado actual y símbolo de entrada.
• q₀ ∈ Q es el estado inicial.
• F ⊆ Q es el conjunto de estados finales o de aceptación.

2. Tabla de Transición de Estados

Podemos representar la función de transición de estados mediante una tabla. Esta tabla muestra los cambios de estado que producen las entradas. En la celda correspondiente al estado qᵢ y la entrada eₖ, se coloca el estado qⱼ tal que δ(qᵢ, eₖ) = qⱼ.

3. Diagrama de Transición de una MEF

Se utiliza un diagrama de transición para describir gráficamente la función de transición de una MEF. Es un grafo dirigido etiquetado G = (Q, R) asociado a la máquina, donde:

• El conjunto de vértices es Q (los estados).
• Existe un arco (arista dirigida) del estado qᵢ al estado qⱼ etiquetado con el símbolo de entrada e<0xE2><0x82><0x96> si y solo si δ(qᵢ, e<0xE2><0x82><0x96>) = qⱼ.

4. Función de Transición Extendida (δ*)

Dada una máquina M = (Q, Σ, δ, q₀, F), la extensión de la función de transición de estados, denotada como δ*, es una función δ*: Q × Σ* → Q definida recursivamente como sigue:

1. δ*(q, ε) = q, donde ε es la cadena vacía. (Condición 1: Si la máquina no procesa entradas, no cambia de estado).
2. δ*(q, wa) = δ(δ*(q, w), a), donde q ∈ Q, w ∈ Σ* y a ∈ Σ. (Condición 2: Determina el estado resultante tras procesar una cadena w seguida de un símbolo a).

También se puede definir para conjuntos de estados:

3. Si P ⊆ Q y w ∈ Σ*, entonces δ*(P, w) = ∪_{q ∈ P} δ*(q, w). (Condición 3: Define δ* para ser aplicada a conjuntos de estados y secuencias de entradas).

5. Lenguaje Aceptado por un Autómata Finito (AFD)

El lenguaje L(M) aceptado por un Autómata Finito Determinista (AFD) M = (Q, Σ, δ, q₀, F) es el conjunto de todas las cadenas de entrada que, al ser procesadas desde el estado inicial q₀, llevan a la máquina a un estado de aceptación en F.

L(M) = {w ∈ Σ* | δ*(q₀, w) ∈ F}

6. Equivalencia de Autómatas Finitos

Dos autómatas finitos, AF1 y AF2, son equivalentes si y solo si aceptan el mismo lenguaje, es decir, L(AF1) = L(AF2).

7. Relación Binaria Compatible con un AFD

Una relación binaria R ⊆ Q × Q, definida en el conjunto de estados Q de un AFD con alfabeto Σ, es compatible con el AFD si y solo si para todo par de estados relacionados y cualquier símbolo de entrada, sus estados sucesores también están relacionados:

∀ qᵢ, qⱼ ∈ Q, ∀ e ∈ Σ : (qᵢ R qⱼ → δ(qᵢ, e) R δ(qⱼ, e))

En otras palabras, la relación R es compatible con el AFD cuando dos estados relacionados (qᵢ R qⱼ) tienen, para cualquier entrada e, imágenes (δ(qᵢ, e) y δ(qⱼ, e)) que también están relacionadas.

8. Método Formal para Analizar la Compatibilidad

Para verificar la compatibilidad de una relación R con un AFD:

1. Considerar todos los pares de estados distintos (qᵢ, qⱼ) tales que qᵢ R qⱼ. (Si qᵢ = qⱼ, la condición siempre se cumple).
2. Para cada uno de estos pares y para cada símbolo de entrada e ∈ Σ, calcular los estados sucesores δ(qᵢ, e) y δ(qⱼ, e).
3. Verificar si estos estados sucesores están relacionados según R, es decir, si δ(qᵢ, e) R δ(qⱼ, e).
4. Si la condición se cumple para todos los pares y todas las entradas, la relación R es compatible con el AFD.

9. Método Práctico para Analizar la Compatibilidad (usando Tabla de Transición)

• Organizar la tabla de transición de modo que los estados relacionados por R estén en filas consecutivas (o agrupados).
• Para cada par de filas correspondientes a estados relacionados (qᵢ, qⱼ), destacar en cada columna (para cada entrada e) las imágenes δ(qᵢ, e) y δ(qⱼ, e).
• En cada columna, analizar si el par de imágenes destacadas está relacionado según R.

10. Relación de Congruencia

Una relación binaria R<0xE1><0xB5><0xA8> ⊆ Q × Q, definida en el conjunto de estados Q de un Autómata Finito (AF) con alfabeto Σ, es una congruencia para el AF si cumple dos condiciones:

1. R<0xE1><0xB5><0xA8> es una relación de equivalencia (reflexiva, simétrica y transitiva).
2. R<0xE1><0xB5><0xA8> es compatible con el AF (según la definición del punto 7).

Como la relación R<0xE1><0xB5><0xA8> es una equivalencia, determina una partición del conjunto de estados Q en clases de equivalencia, formando el conjunto cociente Q/R<0xE1><0xB5><0xA8>.

11. Máquina Cociente

Si M = (Q, Σ, δ, q₀, F) es un AF y R<0xE1><0xB5><0xA8> es una congruencia para M, entonces se puede definir el Autómata Finito Cociente M' = (Q', Σ, δ', q₀', F') como:

• Q' = Q/R<0xE1><0xB5><0xA8> (el conjunto de clases de equivalencia de Q según R<0xE1><0xB5><0xA8>).
• Σ es el mismo alfabeto.
• δ': Q' × Σ → Q' definida como δ'([qᵢ], a) = [δ(qᵢ, a)], donde [q] denota la clase de equivalencia de q.
• q₀' = [q₀] (la clase de equivalencia del estado inicial original).
• F' = {[q] ∈ Q' | q ∈ F} (el conjunto de clases de equivalencia cuyos miembros pertenecen a F).

La máquina cociente M' es equivalente a la máquina original M (acepta el mismo lenguaje) y a menudo tiene un número menor de estados (es minimizada si la congruencia es la de Nerode).

12. Autómatas Finitos y Gramáticas Regulares

Existe una estrecha relación entre los Autómatas Finitos y las Gramáticas Regulares (Tipo 3 en la jerarquía de Chomsky).

Teorema 1: Para cada Autómata Finito Determinista (AFD) M = (Q, Σ, δ, q₀, F), existe una gramática regular G = (N, Σ, S, P) tal que el lenguaje generado por la gramática es igual al lenguaje aceptado por el autómata: L(G) = L(M).

13. Autómatas Finitos No Deterministas (AFN)

Un Autómata Finito No Determinista (AFN) es una quíntupla M = (Q, Σ, δ, q₀, F), similar al AFD, pero con una diferencia clave en la función de transición:

• La función de transición δ mapea un par de estado y símbolo de entrada a un conjunto de posibles estados siguientes: δ: Q × Σ → 2Q (donde 2Q es el conjunto potencia de Q).

Esto significa que para un estado y un símbolo de entrada dados, el autómata puede transicionar a cero, uno o múltiples estados simultáneamente.

14. Lenguaje Aceptado por un AFN

El lenguaje L(M) asociado a un AFN M = (Q, Σ, δ, q₀, F) es el conjunto de cadenas de entrada w ∈ Σ* tales que, al procesar w desde el estado inicial q₀, existe al menos una secuencia de transiciones que conduce a un conjunto de estados que contiene al menos un estado final o de aceptación.

La función de transición extendida δ* para AFN se define como δ*: Q × Σ* → 2Q. El lenguaje es:

L(M) = {w ∈ Σ* | δ*(q₀, w) ∩ F ≠ ∅}

(Donde δ*(q₀, w) es el conjunto de todos los estados posibles alcanzados después de procesar w desde q₀, y ∅ representa el conjunto vacío).