Expresiones Regulares

Definición.

Las expresiones regulares pueden definir de forma exacta los mismos lenguajes que describen los distintos tipos de autómatas: los lenguajes regulares. Sin embargo, las expresiones regulares ofrecen algo que los autómatas no proporcionan: una forma declarativa para expresar las cadenas que deseamos aceptar.

Antes de describir la notación de las expresiones regulares, tenemos que estudiar las tres operaciones sobre los lenguajes que representan los operadores de las expresiones regulares. Estas operaciones son: 

1. La unión de dos lenguajes L y M, designada como L ∪ M, es el conjunto de cadenas que pertenecen a L, a M o a ambos. 

Por ejemplo, si L = {001,10,111} y M = {ε,001}, entonces L ∪ M = {ε,10,001,111}.

2. La concatenación de los lenguajes L y M es el conjunto de cadenas que se puede formar tomando cualquier cadena de L y concatenándola con cualquier cadena de M. Recuerde la Sección 1.5.2, donde definimos la concatenación de una pareja de cadenas; el resultado de la concatenación es una cadena seguida de la otra. Para designar la concatenación de lenguajes se emplea el punto o ningún operador en absoluto, aunque el operador de concatenación frecuentemente se llama “punto”.

Por ejemplo, si L = {001,10,111} y M = {ε,001}, entonces L.M, o simplemente LM, es {001,10,111,001001,10001,111001}. Las tres primeras cadenas de LM son las cadenas de L concatenadas con ε. Puesto que ε es el elemento identidad para la concatenación, las cadenas resultantes son las mismas cadenas de L. Sin embargo, las tres últimas cadenas de LM se forman tomando cada una de las cadenas de L y concatenándolas con la segunda cadena de M, que es 001. Por ejemplo, la concatenación de la cadena 10 de L con la cadena 001 de M nos proporciona la cadena 10001 para LM.

3. La clausura (o asterisco, o clausura de Kleene)1 de un lenguaje L se designa mediante L∗ y representa el conjunto de cadenas que se pueden formar tomando cualquier número de cadenas de L, posiblemente con repeticiones (es decir, la misma cadena se puede seleccionar más de una vez) y concantenando todas ellas.

Por ejemplo, si L = {0,1}, entonces L∗ es igual a todas las cadenas de 0s y 1s. Si L = {0,11}, entonces L∗ constará de aquellas cadenas de 0s y 1s tales que los 1s aparezcan por parejas, como por ejemplo 011, 11110 y ε, pero no 01011 ni 101. Más formalmente, L∗ es la unión infinita ∪i≥0 Li , donde L0 = {ε}, L1 = L y Li , para i > 1 es LL···L (la concatenación de i copias de L).

Construcción de expresiones regulares.

las expresiones regulares válidas, sino que para cada expresión regular E, describimos el lenguaje que representa, al que denominaremos L(E). 

BASE. El caso básico consta de tres partes:

 1. Las constantes ε y /0 son expresiones regulares, que representan a los lenguajes {ε} y /0, respectivamente. Es decir, L(ε) = {ε} y L(/0) = 0. / 

2. Si a es cualquier símbolo, entonces a es una expresión regular. Esta expresión representa el lenguaje {a}. Es decir, L(a) = {a}. Observe que utilizamos la fuente en negrita para indicar la expresión correspondiente a un símbolo. La correspondencia, por ejemplo, que a hace referencia a a, es obvia. 

3. Una variable, normalmente escrita en mayúsculas e itálicas, como L, representa cualquier lenguaje.

 PASO INDUCTIVO: Existen cuatro partes en el paso de inducción, una para cada uno de los tres operadores y otra para la introducción de paréntesis. 

1. Si E y F son expresiones regulares, entonces E +F es una expresión regular que representa la unión de L(E) y L(F). Es decir, L(E +F) = L(E) ∪ L(F). 

2. Si E y F son expresiones regulares, entonces EF es una expresión regular que representa la concatenación de L(E) y L(F). Es decir, L(EF) = L(E)L(F). Observe que el punto puede utilizarse opcionalmente para explicitar el operador de concatenación, bien como una operación sobre lenguajes o como el operador en una expresión regular. Por ejemplo, 0.1 es una expresión regular que significa lo mismo que 01 y que representa el lenguaje {01}. Sin embargo, nosotros vamos a evitar el uso del punto en la concatenación de expresiones regulares.2 

3. Si E es una expresión regular, entonces E∗ es una expresión regular, que representa la clausura de L(E). Es decir, L(E∗) =  L(E) ∗ .

4. Si E es una expresión regular, entonces (E), una E encerrada entre paréntesis, es también una expresión regular, que representa el mismo lenguaje que E. Formalmente; L  (E)  = L(E).

Video sobre expresiones Regulares.