Fundamentos de la Computación: Autómatas, Expresiones Regulares y Gramáticas Formales

Lenguajes Regulares y Autómatas Finitos

Definiciones y Operaciones Regulares

• Operaciones Regulares: Si A y B son lenguajes, las operaciones básicas son: A ∪ B (Unión), A* (Estrella), A ∘ B (Concatenación).
• Operador Estrella (*): $L^* = L^0 \cup L^1 \cup L^2 \cup \dots$
• Operador Cierre Positivo (+): $L^+ = L L^* = L^1 \cup L^2 \cup \dots$
• Propiedades de ER: $A^* A^* = A^*$, $(A^*)^* = A^*$, $A^* = \varepsilon \cup A^+$.
• Precedencia de Operadores: $()$, $^*$, $\circ$, $\cup$.
• Cierre: Los Lenguajes Regulares (LR) son cerrados por Unión (\u222a) y Concatenación (\u2218).
• Expresiones Regulares (ER): Describen Lenguajes Regulares.
• Alfabeto: $\Sigma$. $R^k$: Concatenación de $k$ veces $R$.

Autómatas Finitos (AF)

Autómata Finito Determinista (AFD)

• Definición: $(Q, \Sigma, \delta, q_0, F)$.
• Características: Una única transición por símbolo. No permite transiciones $\varepsilon$.
• Un lenguaje $L$ es regular si un AFN lo reconoce.

Autómata Finito No Determinista (AFN)

• Definición: $(Q, \Sigma, \delta, q_0, F)$.
• Características: Permite transiciones $\varepsilon$.
• Equivalencia: Existe equivalencia entre ER, AFD y AFN.

Construcciones y Conversiones

Construcción de AFN a partir de ER (Thompson)

• Unión (\u222a): Nuevo estado inicial con $\varepsilon$ a los dos autómatas ($N_1$ y $N_2$). Acepta si $N_1$ o $N_2$ aceptan.
• Concatenación (\u2218): Transición $\varepsilon$ de los estados finales de $N_1$ al estado inicial de $N_2$.
• Cierre Estrella (*): Acepta repeticiones de $A_1$. Nuevo estado inicial con $\varepsilon$ al inicio de $N_1$. Los estados finales también tienen $\varepsilon$ al inicio de $N_1$.

Conversión AFN a AFD (Método de Subconjuntos)

• El AFD resultante puede tener hasta $2^n$ estados (donde $n$ es el número de estados del AFN).
• Estado Inicial $q'_0$: Conjunto de estados alcanzables desde $q_0$ (clausura $\varepsilon$).
• Función de Transición $\delta'$: $\delta'(q_0, q_1, a) = \varepsilon$-clausura($\delta(q_0, a) \cup \delta(q_1, a)$).
• Estados Finales $F'$: Subconjuntos que contienen un estado final del AFN.

Conversión AFN a ER (Eliminación de Estados)

• Nuevo $q_0$ y $q_f$ con transiciones $\varepsilon$ a los estados antiguos.
• Se eliminan estados hasta quedar solo con $q_0$ y $q_f$.
• Fórmula de Eliminación: $R_{new} = R_1 (R_2)^* R_3 \cup R_4$.
• $R_1$: Expresión que lleva al estado a eliminar.
• $R_2$: Bucle sobre ese estado (si existe). Ojo: bucles a otro lado se unen (\u222a).
• $R_3$: Expresión que sale del estado a eliminar.
• $R_4$: Expresión que ya existía entre los estados conectados.

Gramáticas Formales y Lenguajes

Conceptos Generales

• Gramáticas: $(V, T, S, R)$. $V$: Variables, $T$: Terminales, $S$: Símbolo inicial, $R$: Reglas de Producción.
• Derivación: Método para describir un lenguaje.
• Árbol de Análisis Sintáctico: Representación visual de la derivación.
• Ambigüedad: Una cadena tiene dos o más árboles de análisis sintáctico (o dos derivaciones más a la izquierda o dos derivaciones más a la derecha).

Gramáticas Regulares (GR)

• Reglas: $X \to aY$, $X \to a$, $X \to \varepsilon$.
• Equivalencia: Existe equivalencia entre AFD y Gramáticas Regulares.
• Conversión AFD → GR: Genera una Gramática Regular equivalente.
• Conversión GR → AFD: Genera un AFN equivalente.

Gramáticas Libres de Contexto (GLC)

• Ejemplo de regla: $A \to 0A1 \mid B$, $B \to \#$.

Forma Normal de Chomsky (FNC)

Las reglas deben ser de la forma: $A \to BC$, $A \to a$, $S \to \varepsilon$ (solo el símbolo inicial $S$ puede generar $\varepsilon$).

1. Paso 1: Nueva variable $S_0 \to S$.
2. Paso 2: Eliminar $\varepsilon$. Donde aparezca $A$ en el lado derecho, se crean variantes.
3. Paso 3: Eliminar producciones unitarias ($A \to B$). Sustituir en $A$ todas las reglas de $B$.
4. Paso 4: Eliminar reglas largas ($A \to BCD$) y reglas mixtas ($A \to aB$), creando nuevas variables intermedias.

Lema de Bombeo para Lenguajes Regulares (LReg)

El Lema de Bombeo se utiliza para demostrar que un lenguaje no es regular.

Condiciones del Lema

Si suponemos que $L$ es regular, existe una longitud de bombeo $P$. Para toda cadena $w \in L$ con longitud $|w| \ge P$, existen cadenas $x, y, z$ (con $w=xyz$) que cumplen:

1. Para todo $i \ge 0$, $xy^i z \in L$ (Se puede repetir o eliminar el bloque 'y', y la cadena resultante sigue perteneciendo).
2. $|y| > 0$ (El bloque que bombea no es vacío).
3. $|xy| \le P$ ($y$ está en los $P$ primeros caracteres).

Proceso de Demostración

1. 1ro: Suponer que $L$ es regular.
2. 2do: Entonces existe $P$ que cumple las condiciones del lema.
3. 3ro: Escoger una cadena $w$ que dependa de $P$ (ej. $w = a^P b^P$).
4. 4to: Dividir $w$ según las condiciones (especialmente $|xy| \le P$).
5. 5to: Bombear $y$ (usar $i=0$ o $i=2, \dots$) y verificar si la cadena resultante $xy^i z$ sigue perteneciendo a $L$.

Conclusión: Si $xy^i z \notin L$, el lenguaje no es regular.

Autómata de Pila (AP)

Definición y Transiciones

• Un AP es un Autómata Finito No Determinista (AFN) con una pila.
• Criterio de Aceptación: Se acepta si procesa toda la entrada y se llega a un estado final.
• Transiciones (Lee, Desapila → Apila):
  • $a, b \to c$: Lee $a$, desapila $b$, apila $c$.
  • $a, \varepsilon \to c$: Lee $a$, no desapila nada, apila $c$.
  • $a, b \to \varepsilon$: Lee $a$, desapila $b$, no apila nada.
  • $\varepsilon, b \to \varepsilon$: No lee entrada, desapila $b$, no apila nada.
• Inicialización de la Pila: Del estado inicial al primer estado, se pone: $\varepsilon, \varepsilon \to \$ (apila el símbolo de fondo de pila). En el estado final, $\varepsilon, \$ \to $\varepsilon$ (vacía el fondo de pila).

Conversión GLC a AP

Si en la regla de la GLC es de tamaño 2 o más, se hace un bucle con transiciones, empezando de derecha a izquierda.