Lenguajes Regulares, Expresiones Regulares y Autómatas Finitos

Lenguajes sobre Alfabetos

Consideremos el alfabeto Σ = {a, b}. Para todo número natural n, hay solo un número finito de palabras sobre Σ cuya longitud es n. Dichas cadenas se pueden obtener lexicográficamente. Numeramos Σ como 0, después numeraremos las palabras de longitud 1, y en general las de longitud n+1 después de las de longitud n. Por ejemplo: Σ -> 0, a -> 1, b -> 2, aa -> 3, ab -> 4...

• De manera más general, suponiendo que tenemos un alfabeto arbitrario Σ. Puesto que todos los alfabetos son finitos, podemos asignar un orden arbitrario a los caracteres pertenecientes a Σ. Así, sin pérdida de generalidad, podemos escribir Σ = {a₀, a₁, a₂...a_n} y numeramos las palabras de Σ de la misma forma: Σ -> 0, a₁ -> 1, a₂ -> 2, ... a_n -> n, a₁a₁ -> n+1 y así sucesivamente.
• Para todo alfabeto Σ, Σ^* es infinito numerable -> |Σ^*| = |ℕ|. El conjunto de todos los lenguajes sobre Σ = 2^Σ* NO es numerable.

Lenguajes Regulares y Expresiones Regulares

Lenguajes Regulares

Sea Σ un alfabeto. El conjunto de los lenguajes regulares sobre Σ se define recursivamente como sigue:

1. ∅ es un lenguaje regular (lenguaje vacío).
2. {ε} es un lenguaje regular (lenguaje cuyo elemento es la cadena vacía).
3. Para todo a ∈ Σ, {a} es un lenguaje regular.
4. Si A y B son lenguajes regulares, entonces A ∪ B, A·B y A^* son lenguajes regulares.
5. Ningún otro lenguaje sobre Σ es regular.

Los lenguajes regulares solo se pueden obtener de los casos básicos mediante un número finito de aplicaciones de las operaciones del apartado d). Por ejemplo, son lenguajes regulares con Σ = {a, b}: ∅, {ε}, {a}, {b}, {a, b} = {a} ∪ {b}, {ab} = {a}·{b}, {a, b, ab}, {aⁱ / i ≥ 0} = {a}^*, L1 = {aⁱb^j / i ≥ 0, j ≥ 0} = {a}^*·{b}^*, {(ab)ⁱ / i ≥ 0} = ({a}·{b})^*, Σ^* = {a, b}^* es el lenguaje más grande que podemos hacer sobre Σ y es regular.

NO es un lenguaje regular, en cambio, L2 = {aⁱbⁱ / i ≥ 0}.

El subconjunto de un lenguaje regular no tiene por qué ser regular. Por ejemplo, L2 está contenido en L1 de los ejemplos anteriores, y L1 es regular y L2 no.

Ejemplo: Σ = {a, b, c} -> el lenguaje L de todas las cadenas sobre Σ que no contengan ninguna subcadena ac, ¿es regular? Sí, {c}^*({a}∪{b}·{c}^*)^*.

Expresiones Regulares

Las expresiones regulares denotan lenguajes regulares. Por ejemplo: a ∪ b es una expresión que denota {a} ∪ {b} = {a, b}.

Definición recursiva de lo que es una expresión regular sobre el alfabeto Σ:

1. ∅ y ε son expresiones regulares.
2. a es una expresión regular para todo a ∈ Σ.
3. Si r y s son expresiones regulares, entonces r ∪ s, r·s y r^* también lo son.
4. Ninguna otra secuencia de símbolos es una expresión regular.

Solo son expresiones regulares aquellas obtenidas de los puntos 1) y 2) mediante operaciones del punto 3).

L(r) es el lenguaje generado por r. L(r) es siempre regular. Dos expresiones regulares son equivalentes si: L(r) = L(s).

Ejemplos con el formato: LENGUAJE REGULAR EXPRESIÓN REGULAR; {ab} ab, {a, b, ab} a ∪ b ∪ ab, {aⁱ / i ≥ 0} a^*, Σ^* = {a, b}^* (a ∪ b)^*.

Teorema (SIMPLIFICAR): sean r, s y t expresiones regulares sobre el mismo alfabeto Σ. Entonces:

• r ∪ s = s ∪ r
• r ∪ ∅ = r = ∅ ∪ r
• r ∪ r = r
• r·ε = ε·r = r
• r∅ = ∅r = ∅
• (rs)t = r(st)
• r(s ∪ t) = rs ∪ rt
• (r ∪ s)t = rt ∪ st
• r^* = r^** = r^*r^* = (ε ∪ r)^* = r^*(r ∪ ε) = (r ∪ ε)r^* = ε ∪ rr^*
• (r ∪ s)^* = (r^* ∪ s^*)^* = (r^*s^*)^* = (r^*s)^*r^* = r^*(sr^*)^*
• r(sr)^* = (rs)^*r
• (r^*s)^* = ε ∪ (r ∪ s)^*s
• (rs^*)^* = ε ∪ r(r ∪ s)^*
• s(r ∪ ε)^*(r ∪ ε) ∪ s = sr^*
• r·r^* = r^*·r = r⁺
• r^* = r⁺ ∪ ε
• rr^* = r⁺

Autómata Finito Determinista (AFD)

Un AFD M = (Q, Σ, s, F, δ) es una colección de 5 elementos:

1. Un alfabeto de entrada Σ.
2. Una colección finita de estados Q (conjunto finito no vacío).
3. Un estado inicial s (o estado de arranque).
4. Una colección F de estados finales o de aceptación.
5. Una función δ: Q x Σ -> Q que determina el único estado siguiente para el par (q_i, a) correspondiente al estado actual y la entrada (función de transición).

Un AFD se puede representar mediante un diagrama de estados, que es un gráfico dirigido cuyos nodos son estados y cuyas aristas son transiciones. Dos círculos concéntricos en un nodo indican un estado final.

Sea cual sea el estado actual y el carácter de la entrada, siempre hay un estado siguiente y este es ÚNICO. Por tanto, para un par (q_i, a) hay 1 y solo 1 valor de la función (estado siguiente). El estado siguiente está totalmente determinado por la información que proporciona el par (q_i, a), por eso es determinista.

Si la función de transición de un AFD no especifica todos los casos, se llama NO completamente especificado.

La función de transición se representa con la tabla de transición.

AFD y Lenguajes

Si M es un AFD, entonces el lenguaje aceptado por M es: L(M) = {w ∈ Σ^* / w es aceptada por M}. Por lo tanto, L(M) es el conjunto de cadenas que hacen que M pase de su estado inicial a un estado de aceptación (aceptaremos cadenas que, empezando en el estado inicial, acabemos de analizarlas en uno final).

Nota: hacemos hincapié en que L(M) está formado por TODAS las cadenas aceptadas por M, y NO que es un conjunto de cadenas que son todas aceptadas por M.

Diremos que dos AFD son equivalentes si L(M1) = L(M2).

Autómata Finito No Determinista (AFN)

Si se permite que desde un estado se realicen cero, una o más transiciones mediante el mismo símbolo de entrada, se dice que el autómata finito es NO determinista. A veces es más conveniente diseñar AFN en lugar de AFD.

Definiremos un AFN mediante una colección de cinco objetos M = (Q, Σ, s, F, Δ) donde:

1. Q es un conjunto finito de estados.
2. Σ es el alfabeto de entrada.
3. s es uno de los estados de Q designado como estado de partida.
4. F es una colección de estados de aceptación o finales.
5. Δ es una relación sobre (Q x Σ) x Q y se llama relación de transición.

Los AFN se pueden representar mediante un diagrama de estados, igual que hacíamos con los AFD, además de con una tabla de transición. Obsérvese que en la tabla de transición, las celdas son conjuntos. Las celdas con ∅ indican que no existe ninguna transición desde el estado actual, mediante la entrada correspondiente. Que para un par estado actual-entrada exista más de un posible estado siguiente indica que se puede elegir entre las distintas posibilidades. Esto es NO determinista.

Si M es un AFN, definimos el lenguaje aceptado por M como: L(M) = {w / w es una cadena aceptada por M} = {w / Δ(s, w) ∩ F ≠ ∅} -> una cadena w es aceptada por M, si M pasa de su estado inicial a un estado final al recorrer w (w es consumida en su totalidad). Para determinar si una cadena pertenece a L(M), se debe recorrer el diagrama de transición correspondiente a M. Debemos encontrar un camino que termine en un estado final cuando haya sido consumida toda la cadena. Durante el recorrido, debemos elegir de forma no determinista la transición de un estado a otro cuando existe más de una para el mismo símbolo. Para afirmar que la cadena NO está en L(M), debemos agotar todas las formas posibles de recorrer el diagrama de estados para dicha cadena.

Los AFN no hacen nada que no hagan los AFD.

Puede ocurrir que se llegue a un momento que no se especifica el camino a seguir puesto que el autómata NO es completamente especificado, entonces rechazamos.

Equivalencia de AFN y AFD

Un autómata M es equivalente a uno M' si L(M) = L(M'). Por cada AFN que acepta un lenguaje, siempre hay un AFD que acepta el mismo lenguaje.

Paso de AFN a AFD

Se empieza en el estado inicial y se van incorporando aquellos estados que son subconjuntos de Q y que surgen como resultado de una transición desde un punto previamente añadido (para cada nuevo estado, se ponen sus transiciones). Paramos cuando ya no aparezcan más estados nuevos. Un AFN de n estados se transformará a lo sumo en un AFD de 2ⁿ estados, pero en la práctica el número de estados aumenta poco.

¿Quiénes son los conjuntos finales del nuevo AFD? Cualquier subconjunto A contenido en Q tal que A ∩ F ≠ ∅, entonces A es estado final del nuevo autómata (cualquier subconjunto de estados que sea estado en el AFD y que contenga un estado final de AFN, es final).

Autómata Finito con Transiciones Épsilon (AFN-ε)

Podemos ampliar la definición de un AFN para incluir transiciones de un estado a otro que no dependan de ninguna entrada. Estas son las transiciones épsilon: se llaman así porque al realizarse no consumen ningún símbolo de la entrada.

En una tabla de transiciones, ε se pone como si fuera un símbolo más.

Se puede sistematizar el proceso para calcular el conjunto de estados siguientes en un AFN con transiciones épsilon. Para todo estado q ∈ Q, definimos el épsilon-cierre de q como: ε-c(q) = {p / p es accesible desde q sin consumir nada en la entrada}.