Fundamentos de Autómatas Finitos: Conversión de AFN a AFD y Expresiones Regulares

Operaciones con Lenguajes Regulares

Las operaciones regulares son la base para construir expresiones y autómatas complejos a partir de componentes más simples. Las principales son la unión, la concatenación y la estrella de Kleene.

Unión (U)

La unión de dos lenguajes, L1 U L2, contiene todas las cadenas que pertenecen a L1, a L2, o a ambos. Para construir un autómata que reconozca esta unión, se crea un nuevo estado inicial con transiciones épsilon (ε) hacia los estados iniciales de los autómatas de L1 y L2.

• Ejemplo: Si L1 = {aⁿ | n ≥ 0} y L2 = {bⁿ | n ≥ 0}, entonces L1 U L2 = {ε, a, aa..., b, bb...}.

Concatenación (·)

La concatenación L1 · L2 forma cadenas tomando una cadena de L1 y siguiéndola con una de L2. Se conecta el estado final del autómata de L1 (que deja de ser final) con el estado inicial del autómata de L2 mediante una transición ε.

• Ejemplo: Si L1 = {a, aa} y L2 = {b, bb}, entonces L1 · L2 = {ab, abb, aab, aabb}.

Estrella de Kleene (*)

La operación L* (estrella) representa cero o más concatenaciones de cadenas del lenguaje L. Se añade un nuevo estado inicial (que también es final para aceptar la cadena vacía ε) y se conectan los antiguos estados finales de L de regreso al antiguo estado inicial con transiciones ε.

• Ejemplo: Si L = {a}, entonces L* = {ε, a, aa, aaa, ...}.

Otras operaciones y precedencia

• Cierre positivo (+): Representa una o más repeticiones. a+ es equivalente a aa*.
• Paréntesis (): Se usan para agrupar y alterar la prioridad de las operaciones.
• Orden de precedencia (de mayor a menor): Paréntesis (), Estrella de Kleene *, Concatenación ·, Unión U.

Conversión de un AFN a un AFD: Construcción de Subconjuntos

El algoritmo de construcción de subconjuntos permite convertir cualquier Autómata Finito No Determinista (AFN), incluso con transiciones ε, en un Autómata Finito Determinista (AFD) equivalente. La idea central es que cada estado del nuevo AFD corresponderá a un subconjunto de estados del AFN original.

El proceso se puede resumir en los siguientes pasos:

1. Estado Inicial: El estado inicial del AFD es el subconjunto que contiene al estado inicial del AFN y todos los estados alcanzables desde él mediante transiciones ε (su ε-clausura).
2. Creación de Estados del AFD: Cada estado en el AFD representa un subconjunto único de estados del AFN.

3. Cálculo de Transiciones: Para cada estado del AFD (que es un subconjunto R de estados del AFN) y para cada símbolo a del alfabeto, la transición δ(R, a) se calcula como la ε-clausura del conjunto de todos los estados a los que se puede llegar desde cualquier estado en R leyendo el símbolo a.

4. Estados Finales: Cualquier estado del AFD cuyo subconjunto de estados del AFN contenga al menos un estado final del AFN original, se convierte en un estado final del AFD.
5. Estado Pozo (o Trampa): Si durante el cálculo de transiciones se genera un subconjunto vacío {}, este se convierte en un estado "pozo" o "trampa" en el AFD, del cual no se puede salir.
6. Criterio de Parada: El proceso se repite hasta que no se generen nuevos subconjuntos (nuevos estados del AFD) en las transiciones.

Aunque un AFN con |Q| estados puede generar un AFD con hasta 2^|Q| estados, en la práctica solo se consideran los estados que son alcanzables desde el estado inicial.

Concepto de ε-clausura

La ε-clausura de un estado (o conjunto de estados) representa "todos los lugares donde se puede estar sin leer ningún símbolo de entrada". Es el conjunto de todos los estados alcanzables a través de cero o más transiciones ε.

Expresiones Regulares y sus Propiedades

Una expresión regular es una secuencia de caracteres que define un patrón de búsqueda, representando un lenguaje regular.

• Concatenación: ab se lee una cadena después de la otra.
• Unión: a|b (o aUb) representa cadenas que son 'a' o 'b'.
• Estrella de Kleene: a* representa cero o más repeticiones de 'a'.

Propiedades Algebraicas

• Asociatividad de la Unión: R1 U (R2 U R3) = (R1 U R2) U R3
• Asociatividad de la Concatenación: R1 · (R2 · R3) = (R1 · R2) · R3
• Distributividad: R1 · (R2 U R3) = R1·R2 U R1·R3
• Identidades: R U ∅ = R, R · ε = R, R · ∅ = ∅
• Idempotencia: ((R*)*) = R*

Equivalencia entre Autómatas y Expresiones Regulares

Los autómatas finitos y las expresiones regulares son formalismos equivalentes: para cualquier expresión regular, existe un autómata finito que la reconoce, y viceversa.

De Expresión Regular a AFN (Construcción de Thompson)

Este método construye un AFN a partir de una expresión regular de forma recursiva, siguiendo el orden de las operaciones (de adentro hacia afuera, de izquierda a derecha). Se definen construcciones para las operaciones básicas:

• Caso R1 U R2: Unión.
• Caso R1 · R2: Concatenación.
• Caso R*: Estrella de Kleene.

De Autómata Finito a Expresión Regular (Eliminación de Estados)

Este proceso se realiza en dos fases: AF → AFNG → ER.

1. Convertir AF a AFNG (Autómata Finito No Determinista Generalizado):
   • Se añade un nuevo estado inicial con una transición ε al antiguo estado inicial.
   • Se añade un nuevo estado de aceptación único, con transiciones ε desde los antiguos estados de aceptación (que dejan de ser finales).
   • Si existen múltiples transiciones entre dos estados p y q, se combinan en una sola transición con una expresión regular que es la unión de sus etiquetas (ej. Rpq = Rpq U a).
   • Se añade una transición con etiqueta ∅ entre estados que no están conectados.

2. Eliminar estados intermedios: Se eliminan progresivamente todos los estados intermedios del AFNG hasta que solo queden el estado inicial y el final, conectados por una única transición cuya etiqueta es la expresión regular equivalente al autómata original.

Relación entre Gramáticas Regulares y Autómatas Finitos

Las gramáticas regulares son otro formalismo equivalente a los autómatas finitos. Una gramática G = (V, T, P, S), donde V es el conjunto de variables, T el de terminales, P las reglas de producción y S el símbolo inicial, es regular si sus reglas tienen la forma X → aY o X → a (o X → ε).

De AFD a Gramática Regular

Se puede construir una gramática regular a partir de un AFD de la siguiente manera:

• Variables (V): Corresponden a los estados del AFD (Q).
• Terminales (T): Corresponden al alfabeto del AFD (Σ).
• Símbolo Inicial (S): Corresponde al estado inicial del AFD (q₀).
• Reglas de Producción (P):
  • Si en el AFD existe una transición δ(q, a) = q', se crea la regla q → aq'.
  • Si un estado q es un estado final (q ∈ F), se añade la regla q → ε.

De Gramática Regular a AFN

Inversamente, se puede construir un AFN a partir de una gramática regular:

• Estados (Q): Corresponden a las variables de la gramática más un nuevo estado final único qf (Q = V ∪ {qf}).
• Alfabeto (Σ): Corresponde a los terminales de la gramática (T).
• Estado Inicial (q₀): Corresponde al símbolo inicial de la gramática (S).
• Estados Finales (F): El conjunto que contiene únicamente al nuevo estado final {qf}.
• Transiciones (δ):
  • Para cada regla A → aB, se añade una transición de A a B con la etiqueta a.
  • Para cada regla A → a, se añade una transición de A al estado final qf con la etiqueta a.
  • Si existe la regla A → ε, el estado correspondiente a A se convierte en un estado de aceptación.