Ahora vamos a centrar nuetra atención a lo que llamaremos una expresión regular, esta sirve como una descripcion algebraica de un lenguaje, de un lenguaje regular, la gran ventaja de trabajar con expresiones regurales en vez de con automatas que es las primeras te permiten ver visulamente (o de forma declarativa) las cadenas que vamos a aceptar.

---

---

Operaciones

Antes de nada veamos las operaciones en las expresiones regulares:

Unión:

Veamos un ejemplo:

Concatenación:

La concatenación es el conjunto de todos las cadenas que se crean de concatenar cualquiera de las cadenas de los dos lenguajes.

Veremos un ejemplo:

Recuerda que epsilon es la «identidad» de las concatenaciones, es decir, que calculo la cadena concatenada con epsilon es la misma cadena.

Cerradura de Kleene:

La cerradura es una operacion muy importante, esta te devuelve todos los strigns que pueden ser formados con al hacer la concatenacion de cualquier cantidad de strings de L.
Veamos un ejemplo, así podemos sacar las primeras iteraciones:

Formas de una RE

Tenemos que saber que no solo hay una forma de expresar las expresiones regulares, por ejemplo, veamos como hacer una RE que sea capaz de recibir cadenas alternantes de 1 y 0.

L = { ε, 0, 1, 101, 10101, 1010101 … 01, 010, 01010 …}

Ejemplos:

(0 + 10*)	L = { 0, 1, 10, 100, 1000, 10000, … }
(0*10*)	L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε)	L = {ε, 0, 1, 01}
(a+b)*	L = { ε, a, b, aa , ab , bb , ba, aaa, …}
(a+b)*abb	L = {abb, aabb, babb, aaabb, abad, …}

---

Propiedades

 

---

De Expresiones Regulares a Autómatas

 

Para lograr esto vamos a ver varias «ε-NFA» base que nos sirve para encontrar RE más complejas:

• Si el ε-NFA describe un RE: a

• Si el ε-NFA describe un RE: Ø

Es deir, es imposible que exista tal RE.

 

• Si el ε-NFA describe un RE: ε

Es decir, acepta cualquier RE.

• Si el ε-NFA describe un RE: RS

Es decir, acepta cualquier RE que sea la concatenación de R seguido de S.

• Si el ε-NFA describe un RE: R*

Es decir, acepta cualquier RE que sea la cerradura de R*.

• Si el ε-NFA describe un RE: R+S

Es decir, acepta cualquier RE que bien R o S.

 

Ejemplo:

Usando esto, como piezas de LEGO, podemos hacer cualquiera RE, veamos todo esto con un ejemplo:

 

• Primer Paso: Hacer un RE que exprese 0 + 1

• Segundo Paso: Hacer un RE que exprese (0 + 1)*

• Tercer Paso: Hacer un RE que exprese (0 + 1)*1(0 + 1)

 

 

 

---

De Automata a Expresión Regular

Los K-Caminos

No haré la explicación pero basado en estos diagramas podemos llegar a :

Recuerda que K no puede ser mas grande que la cantidad de estados:

Espera, espera, ¿Que significa esta «fórmula»?

Para encontrar el Universo de las RE que acepta nuestro autómata tenemos que encontrar los K-Caminos…. Si, esto se explica mejor con un ejemplo…

Encontrar la RE de nuestro DFA (Ejemplo):

Nunca olvides que cuando i=j tenemos que añadir el epsilon.

Ahora si, los K-Caminos:

El pase de diapositivas requiere JavaScript.

 

 

 

 

 

---

Pumping Lemma

Este teorema es tan conocido que ni siquiera quise traducirlo, es demasiado famoso, total, veamos para que sirve el que s considerado el teorema mas importante de las expresiones regulares:

El Pumping Lemma sirve para probar que un lenguaje no es regular, NO ES REGULAR, es decir no nos sirve para probar que sea regular, sino mas bien solo para probar que no es regular.

Digamos que nuestro lenguaje L, es un lenguaje regular, entonces todas las cadenas que pertenezcan a L las podremos dividir en 3 SubStrings usando un numero n (que obviamente tiene que ser menor que la longitud del string original):

• «y» no puede ser un string vacío: y ≠ε
• La concatenación de los primeros dos tiene que ser menor que n: |xy| ≤ n
• Para todas las cadenas con k ≥0, la cadena «x·y^k·z» también esta en el lenguaje L.

Esto es, en español que siempre podremos encontrar una y, no tal lejos del origen que puede ser «repetida o pumped» tantas veces como se quiera (incluso 0 con k=0) y que el string resultante esta aún en L.