Actividad_2 4 y 2 5_lenguajes y automatas - Mauricio axel 20

Vista previa del material en texto

2.4.-Expresiones regulares y sus operaciones.
Las expresiones regulares son una serie de caracteres que forman un patrón, normalmente representativo de otro grupo de caracteres mayores, de tal forma que podemos comparar el patrón con otro conjunto de caracteres para ver las coincidencias. El objetivo de las expresiones regulares es representar todos los posibles lenguajes definidos sobre un alfabeto Σ, en base a una serie de lenguajes primitivos, y unos operadores de composición.
Dado un alfabeto Σ, las expresiones regulares sobre Σ se definen de forma recursiva por las siguientes reglas: 
 1. Las siguientes expresiones son expresiones regulares primitivas:
· ∅
·  λ
· a, siendo a ∈ Σ
    2. Sean α y β expresiones regulares, entonces son expresiones regulares derivadas:
· α+β (unión)
· α.β (o simplemente αβ) (concatenación)
· α* (cierre)
· (α) 
3. No hay más expresiones regulares sobre Σ que las construidas mediante estas reglas. 
Operadores de las expresiones regulares
Las expresiones regulares denotan lenguajes. Por ejemplo, la expresión regular 01*+10* define el lenguaje que consta de todas las cadenas que comienzan con un 0 seguido de cualquier número de 1s o que comienzan por un 1 seguido de cualquier número de 0s.
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 concentrándola con cualquier cadena de M. 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. 
 3. La clausura (o asterisco, o clausura de Kleene) 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 concatenando 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) L^i, donde L^0=(ε),L^1=L y L^i, para i>1 es LL• • •L (la concatenación de i copias de L).
CONSTRUCCIÓN DE EXPRESIONES REGULARES
Caso Base. El caso básico consta de tres partes:
    1. Las constantes ε y ∅ son expresiones regulares, que representan a los lenguajes {ε } y Ø, respectivamente. Es decir, L(ε)= {ε }y L(∅)= ∅.
    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}. 
    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).
    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).
PRECEDENCIA DE LOS OPERADORES EN LAS EXPRESIONES REGULARES
Como con otras álgebras, los operadores de las expresiones regulares tienen un orden de “precedencia” prefijado, lo que significa que se asocian con sus operando en un determinado orden. El orden de precedencia de los operadores es el siguiente:
    1. El operador asterisco (*) es el de precedencia más alta. Es decir, se aplica sólo a la secuencia más corta de símbolos a su izquierda que constituye una expresión regular bien formada.
    2. El siguiente en precedencia es el operador de concatenación, o “punto”. Después de aplicar todos los operadores * a sus operando, aplicamos los operadores de concatenación a sus operando. Es decir, todas las expresiones yuxtapuestas (adyacentes sin ningún operador entre ellas). Dado que la concatenación es una operación asociativa, no importa en qué orden se realicen las sucesivas concatenaciones, aunque si hay que elegir, las aplicaremos por la izquierda. 
    3. Por último, se aplican todos los operadores de unión (+) a sus operando. Dado que la unión también es asociativa, de nuevo no importa en que orden se lleven a cabo, pero supondremos que se calculan empezando por la izquierda.
En ocasiones no se desea que una expresión regular sea agrupada según la precedencia de los operadores. En dicho caso, se puede emplear paréntesis ( ) para agrupar los operando de la forma que se desee. Además, nunca está de más encerrar entre paréntesis los operando que se quieran agrupar, incluso aunque la agrupación deseada sea la prevista por las reglas de precedencia.
2.5 Generar cadenas a partir de una Expresión Regular.
En algunos lenguajes de programación, las expresiones regulares sirven para detectar patrones en distintas cadenas de texto. Para los programadores, esas expresiones regulares facilitan su labor en un solo paso. 
Un ejemplo muy sencillo es la comprobación vía expresión regular que los datos rellenados por los usuarios en un formulario son correctos o no. Alguien puede utilizar un breve formulario para recabar el nombre, los apellidos y el teléfono de contacto de sus clientes, y que algunos de ellos no cumplimenten bien este ultimo campo. La forma rápida de comprobarlo es a través de una expresión regular. Los desarrolladores acostumbrados a utilizar Perl para sus proyectos conocen a la perfección estas herramientas para alcanzar objetivos mediante sencillos atajos.
De todas formas los programadores de Perl no son los únicos desarrolladores que pueden aprovecharse de las ventajas de las expresiones regulares. Los profesionales JavaScript también pueden disfrutar de estas expresiones regulares, concretamente para hacer comprobaciones determinadas en las distintas cadenas de texto a partir de un patrón que se puede resumir en una expresión abierta. También se utilizan en herramientas de analíticas como Google Analytics.
Una expresión regular usa caracteres y meta caracteres para definir, de forma abierta, patrones concretos en cadenas de texto. Esos caracteres, combinados unos con otros de forma especial, permiten extraer patrones o elementos concretos de esa cadena para buscar o manipular el texto (identificadores, correos electrónicos…). En el caso de JavaScript, hay dos tipos de expresiones regulares:
● Expresiones regulares mediante una cadena literal para encontrar un patrón: para ello se usa el constructor de objeto RegExp. Para crear un literal RegExp se utiliza esta expresión: var re = /regular expression/;. El patrón de expresión regular se encuentra entre la apertura y el cierre de las barras diagonales, una estructura que suele ser habitual y obligatoria.
● Expresiones regulares de aplicación en varias cadenas: expReg.test(cadena). Si existe coincidencia, sedevuelve true; y si no existe una coincidencia ente la expresión y un posible patrón, se devuelve false.
Algunos elementos esenciales para hacer expresiones regulares en JavaScript:
● ^: el emparejamiento se debe realizar desde el principio de la cadena.
● [A-Z]: cualquier carácter entre la A y la Z mayúsculas.
● {1,2}: uno o dos caracteres.
● \s: un espacio en blanco.
● \d: un dígito.
● {4}: cuatro dígitos.
● \s: un espacio en blanco.
●([B-D]|[F-H]|[J-N]|[P-T]|[V-Z]): cualquier carácter entre la B y la Z mayúsculas, excepto las vocales.
● {3}: tres caracteres.
● $: el emparejamiento se debe realizar hasta el final de la cadena.
Casos concretos de uso de expresiones regulares.
Es habitual usar expresiones regulares para detectar si existe una secuencia concreta de letras o palabras o bien números en una cadena determinada. Para conseguir eso sólo es necesario utilizar una expresión regular simple:
var reg = /javascript/;
 “Esto es lenguaje javaScript”.match(reg);
 // devuelve un array de un elemento [“javascript”] porque dentro de la cadena se encuentra un elemento con esa secuencia concreta de letras. En el caso de que no existiera la palabras “javaScript” dentro de la cadena, devolvería un elemento null.
A veces se utiliza el elemento if para buscar coincidencias true o false a partir de una combinación de caracteres y palabras (expresiones) en una cadena completa:
if (“Esto es lenguaje javaScript”.match(/javascript/) {
 // Se devolverá true porque si existe el elemento javaScript en la cadena.
 }
 if (“Esto es lenguaje Objective-C”.match(/javascript/) {
 // Se devuelve false porque no existe el elemento javaScript en la cadena.
 }
Usando el elemento vinculado a la búsqueda de dígitos, las expresiones regulares se pueden utilizar para comprobar si una cadena tiene algún digito concreto, incluso programar expresiones regulares para detectar combinaciones o también repeticiones de una serie de dígitos dentro de una o varias cadenas de texto:
– Búsqueda de un dígito concreto en una cadena de texto: en este caso especial el programador busca si la cadena de texto contiene el número 2. Como sí lo contiene, la expresión regular devuelve lógicamente un [“2”].
“Este número es un 2”.match(/\d/); // Devuelve un [“2”]
– Las expresiones regulares son capaces también de detectar la repetición de uno o varios dígitos dentro de una cadena de texto o una secuencia concreta de números dentro de esa misma cadena de texto. Lo único que es necesario es repetir dentro de la expresión el elemento \d, que debe ir acompañado, tanto en la apertura como el cierre, por el símbolo /:
“Este número es el 242”.match(/\d\d\d/); // Devuelve el [“242”] porque dentro de esa cadena existe una expresión que contiene 3 dígitos seguidos.
– Para la búsqueda de dígitos en distintas cadenas de texto:
/\d{3}/ Busca 3 dígitos en la cadena
/\d{1,5}/ Busca entre 1 y 5 dígitos en la cadena.
/\d{2,}/ Busca 2 dígitos o más en la cadena.
Aquí algunos ejemplos concretos con esta última expresión regular: en el primer ejemplo, la expresión permite buscar dentro de una cadena de texto concreta (en este caso, “1234”), un máximo de dos dígitos, por eso devuelve el elemento [“12”]; en el segundo caso se solicita buscar en la cadena de texto entre uno y tres dígitos, por eso devuelve [“123”]; y en el tercer caso, la expresión está diseñada para buscar dentro de la cadena entre tres y diez dígitos, por eso devuelve cuatro, la cadena de texto completa: [“1234”]. 
“1234”.match(/\d{2}/);
[“12”]
“1234”.match(/\d{1,3}/);
[“123”]
“1234”.match(/\d{3,10}/)
[“1234”]