UNIDAD 2

Expresiones regulares.

2.1.- Definición formal de una ER.

Son patrones utilizados para encontrar una determinada combinación de caracteres dentro de una cadena de texto. En JavaScript, las expresiones regulares también son objetos. Estos patrones se utilizan en los métodos exec y test de RegExp, así como los métodos match, replace, search y split de String. En este capítulo se describe el uso y funcionamiento de las expresiones regulares en JavaScript.

Una expresión regular puede crearse de cualquiera de las dos siguientes maneras:

Utilizando una representación literal de la expresión regular, consistente en un patrón encerrado entre diagonales, como a continuación:   

var re = /ab+c/;

La representación literal ofrece la compilación de la expresión regular cuando se carga el script donde se encuentra. Si la expresión regular permanece constante, utilizar esta forma puede mejorar en rendimiento.

Llamando a la función constructora del objeto RegExp, como a continuación:      

 var re = new RegExp('ab+c');

El uso de la función constructora ofrece la compilación en tiempo de ejecución de la expresión regular. Utilice la función constructora cuando sepa que el patrón de la expresión regular cambiará, o cuando desconozca el patrón y deba obtenerlo de otra fuente, como por ejemplo del usuario.

Una expresión regular ER sobre un alfabeto finito Σ se define recursivamente como sigue:

1. Para todo c ∈ Σ, c es una ER 

2. Φ es una ER

3. Si E1 y E2 son ERs, E1 | E2 es una ER

4. Si E1 y E2 son ERs, E1 · E2 es una ER

5. Si E1 es una ER, E1 ⋆ es una ER

6. Si E1 es una ER, (E1) es una ER Cuando se lee una expresión regular, hay que saber qué operador debe leerse primero. Esto se llama precedencia.

Por ejemplo, la expresión a | b · c ⋆,

¿debe entenderse como

(1) la “⋆” aplicada al resto?

(2) ¿la “|” aplicada al resto?

(3) ¿la “·” aplicada al resto?

La respuesta es que, primero que nada se aplican los “⋆”, segundo los “·”, y finalmente los “|”.

Esto se expresa diciendo que el orden de precedencia es ⋆, ·, |.

Los paréntesis sirven para alterar la precedencia.

Por ejemplo, la expresión anterior, dado el orden de precedencia que establecimos, es equivalente a

a | (b · (c ⋆)). Se puede forzar otro orden de lectura de la ER cambiando los paréntesis, por ejemplo (a | b) · c ⋆. Asimismo, debe aclararse cómo se lee algo como a|b|c, es decir ¿cuál de los dos “|” se lee primero?

Convengamos que en ambos operadores binarios se lee primero el de más a la izquierda (se dice que el operador “asocia a la izquierda”), pero realmente no es importante, por razones que veremos enseguida. Observar que aún no hemos dicho qué significa una ER, sólo hemos dado su sintaxis, pero no su semántica.

Bibliografía;

John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (2001). Automata Theory, Language and Computation. Addison-Wesley Publishing.

Michael Sipser (1997). Introduction to the Theory of Computation. PWS publishing company.

Maigualida Pérez Melgarejo.

  

                                          2.1. Definición formal de una ER.

Es utilizado como un lenguaje para describir patrones en texto que son sencillos pero muy útiles.

Dado un alfabeto Σ, una expresión regular sobre expresión regular sobre Σ se define de forma recursiva:

ER primitivo: Φ, λ, {a | a ЄЄЄ Σ Є}

Si α y β son ER, entonces son también ER: α + β (unión), α β (concatenación), α* (cierre), (α).

No existen otras reglas para la construcción de ER sobre Σ.

Ejemplo de uso.

Por ejemplo, la expresión regular: 01* + 10* denota todas las cadenas que son o un 0 seguido de cualquier cantidad 1's o una 1 seguida de cualquier cantidad de 0's.

Operaciones de los lenguajes:

Unión: Si L y M son dos lenguajes, su unión se denota por L U M.

Concatenación: La concatenación es: LM o L.M.

Cerradura (o cerradura de Kleene): Si L es un lenguaje su cerradura se denota por L *.

Si E es una expresión regular, entonces L(E) denota el lenguaje que define E. Las expresiones se construyen de la manera siguiente:

Las contantes y son expresiones regulares que representan a los lenguajes L (Q) = {Q} y L (Φ) L = Φ respectivamente.

Si a es un símbolo, entonces es una expresión regular que representan al lenguaje: L (a) = {a}.

Bibliografía:

http://10380054.galeon.com/u2.htm

Santiago Reyes Edgarda.

  

2.2.-Diseño en ER.

Unión o Alternativa: Consideremos dos lenguajes diferentes definidos sobre el mismo alfabeto L1 ⊂ W(∑) y L2 ⊂ W(∑). Se denomina unión de ambos lenguajes al lenguaje formado por las palabras de ambos lenguajes:

L1 U L2={ x | x ∈ L1 ó x ∈ L2}

Concatenación: Consideremos dos lenguajes definidos sobre el mismo alfabeto, L1 y L2. La concatenación o producto de estos lenguajes es el lenguaje L1 L2= { xy / x ∈ L1 y x ∈ L2} Las palabras de este lenguaje estarán formadas al concatenar cada una palabra del primero de los lenguajes con otra del segundo.

La concatenación de lenguajes con el lenguaje vació es ΦL = L Φ = Φ

        Potencia de un lenguaje: Se define la potencia i-ésima de un lenguaje a la operación de concatenarlo consigo mismo i veces.

                                   Li= LLL ....L

                                   |------------|

                                   i

Clausura positiva de un lenguaje: Se define la clausura positiva de un lenguaje L: 

                                   ∞

                                   L + = U L i 

                                   i=1

Lenguaje obtenido uniendo el lenguaje; con todas sus potencias posibles excepto Lº. Si L no contiene la palabra vacía, la clausura positiva tampoco

Cierre o Clausura de un lenguaje: Se define el cierre o clausura de un lenguaje L como:

                                    ∞

                                   L* = U Li

                                   i=0

Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles, incluso Lº. Todas las clausuras contienen la palabra vacía.

Existen tres operaciones básicas que se pueden realizar sobre las ER:

Selección de alternativas: Se indica con el operador |(barra vertical). Si r y s son ER, entonces r | s es una ER que define a cualquier cadena que concuerde con una r o una s, también se dice que r | s , es la unión de los lenguajes de r y s y lo podemos definir: L( r | s ) = L( r ) U L( s ). Esta operación se puede extender a más de dos ER.

Concatenación: Se indica con la yuxtaposición de las ER. Si r y s son ER, entonces rs es una ER que define a cualquier cadena que concuerde con la concatenación de r y s , esta operación la podemos definir: L(rs) = L(r)L(s).Esta operación se puede extender a más de dos ER.

Repetición o Cerradura: También se conoce con el nombre de cerradura de Kleene. Se indica con el operador *. Si r es una ER, entonces r* es una ER que define a las cadenas de caracteres representadas por la concatenación repetida de r en n veces, o sea que lo podemos definir como: L(r*) = L(r)*o también lo podemos definir como la unión infinita de conjuntos r :r* n = r 0 r 1 r 2...r n.

Bibliografía;

http://10380054.galeon.com/u2.htm

Marisa Martínez Bautista.

2.3.- Aplicación en problemas reales.

Rodolfo Rodríguez Medina

2.3 aplicaciones en problemas

Las expresiones regulares que facilitan la construcción de un compilador. A menudo se utiliza una expresión regular larga y compleja para validar la sintaxis de un programa. Si el código del programa no concuerda con la expresión regular, el compilador sabe que hay un error de sintaxis dentro del código.

Generalmente convierten la expresión regular a un autómata finito no determinista y después construyen el autómata finito determinista.

1.- Ejemplo:

Si ∑ = {a, b, c} entonces

∑² = {aa, ab, ac, ba, bb, bc, ca, cb, cc}

2.- Ejemplo:

Sea Ꞩ = {0, 1} y L ={01, 1} entonces

L³ = {010101, 01011, 01101, 0111, 10101, 1011, 1101, 111} 

Bibliografías:

https://es.slideshare.net/AnelVeronicaUchihaLP/espresiones-regulares

https://slideplayer.es/slide/1875947/

Blanca Estela Reyes Castillo.