REPORTE U-2 LENG AUT - Mauricio axel 20

Vista previa del material en texto

CARRERA: INGENERIA EN SISTEMAS COMPUTACIONALES
PROFESOR ING. M.C BEDOLLA SOLANO SILVESTRE
MATERIA: LENGUAJES Y AUTOMATAS 1
HORARIO: 15:00 – 16:00 HRS
INTEGRANTES DEL EQUIPO 2:
1. ABARCA LOPEZ ALBERTO JOSUE
2. CANTUN PALACIOS CARLOS ALBERTO
3. LOPEZ ANSELMO MAURICIO AXEL
4. RAMOS PEREZ GUADALUPE INES
UNIDAD 2 EXPRESIONES REGULARES
FECHA DE ENTREGA: 21 DE OCTUBRE DEL 2020
CONTENIDO
Portada	1
Indice	2
Introduccion	3
2.1 definición formal de una expresión regular	4-5
Ejemplo
2.2 diseño de una expresión regular	6-8
Operaciones
Anotaciones
Precedencias y asociatividad
2.3 aplicaciones en problemas reales	8-10
Ejemplos
2.4 investigar las expresiones regulares y sus operaciones	11-14
 2.4.1 Operaciones de las expresiones regulares
 2.4.2 Construcción de una expresión regular
 2.4.3 Precedencia de las operaciones en las expresiones regulares
2.5 Generar cadenas a partir de una expresión regular	15-18
 2.5.1 Casos concretos de uso de una expresión regular
2.6 Obtener una expresión regular a partir de un grupo de cadenas o viceversa	19-28
 2.6.1 Expresiones regulares
 2.6.2 Leyes algebraicas para una expresión regular 
 2.6.3 Construcción de autómata infinito a partir de una expresión regular
 2.6.4 Construcción del autómata finito con transacciones -E
 2.6.5 Construcción del AFND a partir del AFND-E
 2.6.6 Construcción del AFND correspondientes al AFND-E anterior
 2.6.7 Construcción de la expresión regular a partir del autómata
 2.6.8 Eliminación de estados del autómata
 2.6.9 Algoritmo para construir la expresión regular a partir de un autómata
Conclusión	29
Referencias	30
Las expresiones regulares se utilizan para hacer búsquedas contextuales y modificaciones sobre textos. A pesar de que las expresiones regulares estén muy extendidas por el mundo de Unix, no existe un lenguaje estándar de expresiones regulares. Más bien se puede hablar de diferentes dialectos. Existen por ejemplo dos representantes del conocido programa grep, egrep y fgrep. Ambos usan expresiones regulares con capacidades ligeramente diferentes. Perl se puede calificar como el lenguaje con la sintaxis de expresiones regulares más desarrollado. Por suerte todos estos dialectos siguen los mismos principios y en el momento que se han entendido, el resto es sencillo.INTRODUCCIÓN
Las expresiones regulares son una serie de carácter es que forman un patrón, normalmente representativo de otro grupo de carácter es mayor, de tal forma que podemos comparar el patrón con otro conjunto de carácter es para ver las coincidencias.
Las expresiones regulares están disponibles en casi cualquier lenguaje de programación, pero, aunque su sintaxis es relativamente uniforme, cada lenguaje usa su propio dialecto. Si es la primera vez que te acercas al concepto de expresiones regulares (regex para abreviar) te animará saber que, seguro que ya las has usado, aún sin saberlo, al menos en su vertiente más básica. Por ejemplo, cuando en una ventana DOS ejecutamos dir *.* para obtener un listado de todos los archivos de un directorio, estamos utilizando el concepto de expresiones regulares, donde el patrón * coincide con cualquier cadena de caracteres.
2.1 DEFINICIÓN FORMAL DE UNA EXPRESIÓN REGULAR
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.
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: 
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.var re = /ab+c/;
Llamando a la función constructora del objeto RegExp, como a continuación: 
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.var re = new RegExp('ab+c');
Una expresión regular ER sobre un alfabeto finito Σ se define recursivamente como sigue:
1. Para todo c ∈ Σ, c es una ER 
1. Φ es una ER
1. Si E1 y E2 son ERs, E1 | E2 es una ER
1. Si E1 y E2 son ERs, E1 · E2 es una ER
1. Si E1 es una ER, E1 ⋆ es una ER
1. 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.
Dado un alfabeto Σ, una expresión regular sobre expresión regular sobre Σ se define de forma recursiva:
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 Σ.ER primitivo: Φ, λ, {a | a ЄЄЄ Σ Є}
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.EJEMPLO
Operaciones de los lenguajes:
1. Unión: Si L y M son dos lenguajes, su unión se denota por L U M.
1. Concatenación: La concatenación es: LM o L.M.
1. 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}.
El analizador léxico debe analizar e identificar sólo un conjunto finito de cadena válida/token/lexeme que pertenecen al lenguaje de la mano. Busca el modelo definido por las normas del lenguaje.2.2 DISEÑO DE UNA EXPRESIÓN REGULAR
Las expresiones regulares tienen la capacidad de expresar finitos idiomas definiendo un modelo finito de cadenas de símbolos. La gramática definida por las expresiones regulares es conocido como gramática regular. El idioma definido por gramática regular se conoce como idioma habitual.
Expresión regular es una notación para importante especificación de patrones. Cada patrón coincide con un conjunto de cadenas, de modo que las expresiones regulares como nombres para un conjunto de cadenas. Fichas lenguaje de programación puede ser descrita por los idiomas. La especificación de las expresiones regulares es un ejemplo de una definición recursiva. Lenguajes regulares son fáciles de comprender y tener eficacia en su aplicación.
Hay una serie de leyes algebraicas que son obedecidas por las expresiones regulares, que puede ser usado para manipular las expresiones regulares en formas equivalentes.OPERACIONES
Las diferentes operaciones sobre los idiomas disponibles son:
Unión de dos idiomas L y M se escribe como
· L U M = {s | s en L o s es en M}
 La concatenación de dos lenguajes L y M se escribe como
· LM = {st | s es en L y t se encuentra en M}
 La clausura de Kleene un lenguaje L es escrito como
· L* = cero o más apariciones del lenguaje L.
Si r y s son expresiones regulares denotando las lenguas L(r) y L(s), a continuación,ANOTACIONES
· Unión: (r) | (s) es una expresión regular que denota L(r) U L(s)
· Concatenación: (r)(s) es una expresión regular que denota L(r)L(s)
· Cierre Kleene : (R)* es una expresión regular que denota (L(r))*
· (R) es una expresión regular que denota L(r)
PRECEDENCIAS 
Y ASOCIATIVIDAD
· La concatenación (.), y | (pipe) son asociativo
· Tiene la mayor prioridad
· La concatenación (.) tiene la segunda mayor prioridad.
· | (Pipe) tiene la menor prioridad de todos.
· Tokens válidos representan una lengua en expresiones regulares
Si x es una expresión regular, entonces:
· X * significacero o más apariciones de x.
Es decir, puede generar { e, x, xx, xxx, xxxx, ... }
· X+ significa una o más apariciones de x.
Es decir, puede generar { x, xx, xxx, xxxx ... } o x.x*
· X? Medios de una ocurrencia más de x
Es decir, se puede generar un {x} o {e}.
· [A-z] es todo en mayúsculas y minúsculas del alfabeto inglés.
· [A-Z] mayúsculas alfabetos de idioma inglés.
· [ 0-9] es natural dígitos utilizados en matemáticas.
De aparición de símbolos mediante expresiones regulares
· Letra = [a - z] o [A - Z]
· Dígito = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 o [ 0-9]
· Signo = [ + | - ]
Fichas de idioma usando expresiones regulares
· Decimal = (signo)?(dígito)+
· Identificador = (carta) (letra | digit) *
El único problema con el analizador léxico es la forma de verificar la validez de una expresión regular que se utiliza para especificar los patrones de palabras clave de un lenguaje. Una solución es utilizar autómatas finitos para verificación.2.3 APLICACIONES EN PROBLEMAS REALES
Una de las principales aplicaciones de los hermanos Deitel, son 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 construye el autómata finito determinista. Otra aplicación del mismo libro es en los editores de texto donde también encontramos a las expresiones regulares en la biología molecular teniendo en cuenta que hay esfuerzos importantes para tratar de representar cadenas como generadas por expresiones regulares o por lenguajes regulares.
EJEMPLOS
2.4 INVESTIGAR LAS 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
Las expresiones regulares denotan lenguaje. 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.
2.4.1 OPERADORES DE LAS EXPRESIONES REGULARES
Las 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, 11} 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).
2.4.2 CONSTRUCCIÓN DE EXPRESIONES REGULARES
CASO BASE: El caso básico consta de 3 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.
a) 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).
b) 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).
c) 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))*
d) 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).
	
2.4.3 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 su 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 operandos, aplicamos los operadores de concatenación a sus operandos. 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 operandos. 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 operandos 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 porlos 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 último 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, se devuelve 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.
2.5.1 CASOS CONCRETOS DE USO DE EXPRESIONES REGULARES
Es habitual usar expresiones regulares para detectar si existe una secuencia concreta de letras o palabras o mas 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:
a) /\d{3}/ Busca 3 dígitos en la cadena
b) /\d{1,5}/ Busca entre 1 y 5 dígitos en la cadena.
c) /\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”]
2.6 OBTENER UNA EXPRESIÓN REGULAR APARTIR DE UN GRUPO DE CADENAS O VICEVERSA
2.6.1 EXPRESIONES REGULARES
Se denominan expresiones regulares sobre un alfabeto A, a las expresiones que se pueden construir a partir de las siguientes reglas: 
· ∅ es una expresión regular que describe el lenguaje vacío.
· ε es una expresión regular que describe el lenguaje {ε}, esto es el lenguaje que contiene únicamente la cadena vacía.
· Para cada símbolo a ∈ A, a es una expresión regular que describe el lenguaje {a}, esto es el lenguaje que contiene únicamente la cadena a.
· Si r y s son expresiones regulares que describen los lenguajes L(r) y L(s) respectivamente: 
· i) r + s es una expresión regular que describe el lenguaje L(r) ∪ L(s)
· ii) r . s es una expresión regular que describe el lenguaje L(r) . L(s) 
· iii) r* es una expresión regular que describe el lenguaje L(r)* . 
El operador de clausura es el que tiene mayor precedencia, seguido por el operador de concatenación y por último el operador de unión. Las expresiones regulares describen los lenguajes regulares (aquellos reconocidos por autómatas finitos). Por ejemplo, las siguientes son expresiones regulares válidas: 
· a*. b que describe el lenguaje L = {an b / n ≥ 0}.
· (a + b) * que describe el lenguaje L = {x / x ∈ {a, b} *}
2.6.2 LEYES ALGEBRAICAS PARA UNA EXPRESIÓN REGULAR
	Dos expresiones regulares r y s son equivalentes: (r ≡ s) si L(r) = L(s).
	Sean r, s y t expresiones regulares:
	1) r + ∅ ≡ ∅ + r ≡ r
	2) r . ε ≡ ε . r ≡ r
	3) r . ∅ ≡ ∅ . r ≡ ∅
	4) r + s ≡ s + r
	5) (r + s) + t ≡ r + (s + t)
	6) (r . s) . t ≡ r . (s . t)
	7) r . (s + t) ≡ r . s + r . t
	8) (s + t) . r ≡ s . r + t . r
	9) ) r + r ≡ r
	10) ∅ * ≡ ε
	11) r . r* ≡ r* . r
	12) r . r * + ε ≡ r
	13) (r* . s* ) * ≡ (r + s)*
	14) (r* ) * ≡ r *
	
2.6.3 CONSTRUCCIÓN DE AUTÓMATA INFINITOS APARTIR DE UNA EXPRESIÓN REGULAR
Los lenguajes descriptos por expresiones regulares son los lenguajes reconocidos por los autómatas finitos. Existe un algoritmo para convertir una expresión regular en el autómata finito no determinístico correspondiente. 
El algoritmo construye a partir de la expresión regular un autómata con transiciones vacías, es decir un autómata que contiene arcos rotulados con ε. Luego este autómata con transiciones vacías se puede convertir en un autómata finito sin transiciones vacías que reconoce el mismo lenguaje.
2.6.4 CONSTRUCCIÓN DEL AUTÓMATA FINITO CON TRANSICIONES ε.
Si r es una Si r tiene operadores, se dan tres casos dependiendo de la forma de r:
expresión regular con n operadores y sin variables como operandos atómicos,existe un autómata finito no determinístico M con transiciones ε (AFND-ε) que acepta solamente aquellas cadenas que están en L(r). M tiene un estado final, no entran arcos al estado inicial y no salen arcos del estado final.EJEMPLOS
r puede ser una expresión sin operadores (∅, ε o un símbolo) o con operadores (+, ., *). Si r no tiene operadores, entonces:
1) r = r1 + r2
Sean M1 = <E1, A, δ1, e01, {ef1}> y M2 = < E2, A, δ2, e02, {ef2}>, los autómatas correspondientes a r1 y r2. Se construye un nuevo autómata M que une a estos dos autómatas M1 y M2 agregando un estado inicial e0 y un estado final ef0; M = < E1 ∪ E2 ∪ {e0, ef0}, A, δ, e0, {ef0}>. El estado inicial de M tiene transiciones ε a los estados iniciales de M1 y M2; los estados finales de estos autómatas tienen transiciones ε al estado final del autómata M.
2) r = r1 . r2
Sean M1 = <E1, A, δ1, e01, {ef1}> y M2 = < E2, A, δ2, e02, {ef2}>, los autómatas correspondientes a r1 y r2. Se construye un nuevo autómata M, M = < E1 ∪ E2, A, δ, e01, {ef2}> que tiene como estado inicial al estado inicial de M1 y como estado final al estado final de M2; tiene además un arco rotulado ε desde el estado final de M1 al estado inicial de M2.
3) r = r1 *
Sea M1 = <E1, A, δ1, e01, {ef1}> el autómata correspondiente a r1. Se construye un nuevo autómata M, M = < E1 ∪ {e0, ef0}, A, δ, e0, {ef0}>; y se agregan arcos rotulados ε desde e0 al estado inicial de M1 y al estado final de M, y desde el estado final de M1 al estado inicial de M1 y a ef0.
4) Construir el AFND-ε correspondiente a la siguiente expresión regular r = 0 . 0 + 0* . 1
r es de la forma r1 + r2, donde r1 = 0 . 0 y r2 = 0* . 1
r1 se puede expresar como r3 . r4, donde
2.6.5 CONSTRUCCIÓN DEL AFND A PARTIR DEL AFND-Ε
Dado un AFND-ε es posible construir un AFND equivalente sin transiciones vacías que reconoce el mismo lenguaje. Los estados del nuevo autómata son los estados importantes del AFND-ε y el estado inicial del AFND-ε. Se denominan estados importantes aquellos estados a los que llega un arco con un símbolo real como rótulo. El estado inicial es el estado inicial del AFND-ε. 
La función de transición se define teniendo en cuenta que existe una transición del estado importante ei al estado importante ej con el símbolo x, si existe algún estado ek tal que: 
· Se puede llegar desde el estado ei al estado ek con un camino de 0 ó mas transiciones ε; se permite ei = ek
· En el AFND-ε existe una transición del estado ek al estado ej rotulada con el símbolo x. Los estados finales del nuevo autómata son los estados finales del AFND-ε y todos los estados ei del AFND-ε para los cuales existe un camino con transiciones ε, en el AFND-ε, a algún estado final del AFND-ε
1) Construcción del AFND correspondiente al AFND-ε del ejemplo 4. EJEMPLOS
El conjunto de estados está formado por e0 (estado inicial) y por los estados e2, e4, e7 y e10 (estados importantes). Los estados finales son e4 y e10 (existe un camino en el AFND-ε con transiciones ε a un estado final del AFND-ε). El estado inicial es e0. 
· Transiciones para el estado e0: desde el estado e0 se pueden alcanzar con transiciones ε los estados e0, e1, e5, e6, e8 y e9. En el AFND-ε existe una transición de e1 a e2 con 0, una transición de e6 a e7 con 0 y una transición de e9 a e10 con 1. Entonces en el nuevo autómata hay una transición de e0 a e2 con 0, una transición de e0 a e7 con 0 y una transición de e0 a e10 con 1.
· Transiciones para el estado e2: desde el estado e2 se pueden alcanzar con transiciones ε los estados e2 y e3. En el AFND-ε existe una transición de e3 a e4 con 0. Entonces en el nuevo autómata, hay una transición del estado e2 al estado e4 con 0.
· Transiciones para el estado e7: desde el estado e7 se pueden alcanzar con transiciones ε los estados e6, e7, e8 y e9. En el AFND-ε existe una transición de e6 a e7 con 0 y una transición de e9 a e10 con 1. Entonces en el nuevo autómata, hay una transición del estado e7 al estado e7 con 0 y una transición del estado e7 al estado e10 con 1. 
· Transiciones para el estado e4: desde el estado e4 se pueden alcanzar con transiciones ε los estados e4 y e11. Como en el AFND-ε no existen transiciones sobre símbolos reales desde el estado e11, entonces no se agregan transiciones desde el estado e4 en el nuevo autómata.
· Transiciones para el estado e10: desde el estado e10 se pueden alcanzar con transiciones ε los estados e10 y e11. Como en el AFND-ε no existen transiciones sobre símbolos reales desde el estado e11, entonces no se agregan transiciones desde el estado e10 en el nuevo autómata. El autómata correspondiente sin transiciones ε se define AFND = , con δ definida por el siguiente diagrama de transición de estados.
Se puede observar que este autómata es no determinístico. Como ya se ha visto, es posible construir a partir del mismo el autómata finito determinístico equivalente que reconoce el mismo lenguaje.
2.6.6 CONSTRUCCIÓN DEL AFND CORRESPONDIENTE AL AFND - £ ANTERIOR
 
El conjunto de estados está formado por e0 (estado inicial) y por los estados e2, e5 y e9 (estados importantes). El único estado final es e9. El estado inicial es e0. El autómata correspondiente sin transiciones ε se define AFND = <{e0, e2, e5, e9}, {0, 1}, δ, e0, {e9}>, con δ definida por el siguiente diagrama de transición de estados.
Se puede observar que este autómata es no determinístico. Como ya se ha visto, es posible construir a partir del mismo el autómata finito determinístico equivalente que reconoce el mismo lenguaje, que podría ser luego minimizado. Otra posibilidad es simplificar la expresión regular primero para obtener directamente el AFD mínimo.
2.6.7 CONSTRUCCIÓN DE LA EXPRESIÓN REGULAR APARTIR DEL AUTÓNOMA
A partir de cualquier autómata finito es posible obtener una expresión regular que describe el lenguaje reconocido por el autómata. Esta conversión consiste en ir eliminando los estados del autómata uno por uno, reemplazando los rótulos sobre los arcos, que inicialmente son símbolos, por expresiones regulares más complicadas.2.6.8 ELIMINACIÓN DE ESTADOS DEL AUTÓMATA
Se desea eliminar el estado u, pero se deben mantener los rótulos de las expresiones regulares sobre los arcos de modo tal que los rótulos de los caminos entre cualesquiera pares de estados de los estados restantes no cambien.
Si no existe arco de u a u se puede agregar uno rotulado ∅. Los nodos si , para i = 1, 2, ..., n, son nodos predecesores del nodo u, y los nodos tj , para j = 1, 2, ..., m, son nodos sucesores del nodo u. Existe un arco de cada si a u, rotulado por una expresión regular Si , y un arco de u a cada tj rotulado por una expresión regular Tj . Si se elimina el nodo u, estos arcos y el arco rotulado U desaparecerán. Para preservar estas cadenas, se debe considerar cada par si y tj y agregar al rótulo del arco de si a tj , una expresión regular que represente lo que desaparece. En general se puede suponer que existe un arco rotulado Rij de si a tj para i = 1, 2, ..., n y j = 1, 2, ..., m. Si el arco de si a tj no está presente se puede agregar con rótulo ∅. El conjunto de cadenas que rotulan los caminos de si a u, incluyendo el ciclo de u a u, y luego de u a tj , se puede describir por la expresión regular SiU * Tj . Por lo tanto, después de eliminar u y todos los arcos que llegan y salen de u, se debe reemplazar el rótulo Rij del arco de si a tj por la expresión regular
Rij + SiU * Tj
2.6.9 ALGORITMO PARA CONSTRUIR LA EXPRESIÓN REGULAR APARTIR DEL AUTÓMATA 
Los pasos a seguir son los siguientes: 
1) Repetir para cada estado final: 
· Si el estado final es también inicial, eliminar todos los estados excepto el estado inicial. La expresión regular correspondiente es S*.
2) Realizar la unión de las expresiones regulares obtenidas para cada estado final del autómata.
· Si no, eliminar los estados del autómata hasta que queden únicamente el estado inicial y el estado final en consideración. La expresión regular que nos lleva del estado s al estado t es S* U (T + V S* U)* ≡ S* U (T* (V S* U)* ) *.EJEMPLOS
1. Obtenerla expresión regular correspondiente al lenguaje del ejemplo 1.
Paso 1: El único estado final es p3. Como no es inicial se deben eliminar los estados p1 y p2 para que queden únicamente p0 (el estado inicial) y p3 (el estado final en consideración).
Paso 2: La expresión regular correspondiente es: ((1 + 01)(01)* (1 + 00) + 00)(0 + 1)*
2. Obtener la expresión regular correspondiente al lenguaje del ejemplo 2.
Paso 1: Como el autómata tiene dos estados finales, se calculará una expresión regular para cada uno de ellos. El estado final e0 es también inicial. Por lo tanto se deberán eliminar todos los estados que están en el camino de e0 a e0. El único estado a eliminar es e1.
· Eliminación del estado e1:
La expresión regular para el estado e0 es ER1 = (a + ba* b)* El otro estado final es e4. Como no es inicial se deben eliminar los estados e1, e2 y e3 para que queden únicamente e0 (el estado inicial) y e4 (el estado final en consideración). 
La expresión regular para el estado e4 es ER2 = (a + ba* b)* ccc(ccc)* 
Paso 2: La expresión regular correspondiente al autómata se obtiene uniendo las expresiones regulares resultantes para cada estado final. 
ER = ER1 + ER2 = (a + ba* b)* + (a + ba* b)* ccc(ccc)*.
Hemos visto las expresiones regulares POSIX extendido pero una vez que domines éstas también puedes aprender las de Perl, que son parecidas, pero aparte son muchas más potentes, ya que tienen modificadores que hacen de todo.CONCLUSIÓN
Las expresiones regulares permiten comprobar si una cadena de texto se ajusta a un determinado tipo de estructura o patrón. Utilizan un lenguaje de signos propio, y permiten también buscar o remplazar texto, no sólo un texto concreto sino un tipo de texto que se ajuste a un determinado patrón.
Las expresiones regulares no son exclusivas de JavaScript, las usan también otros lenguajes de programación, de hecho, JavaScript las ha importado de ellos. La clase RegExp posee varios métodos que veremos más adelante, los cuales permiten comprobar, buscar o remplazar los elementos del texto.
REFERENCIAS
Anonimo. (20 de Junio de 2005). Desarrolloweb.com. Obtenido de Expresiones Regulares: https://desarrolloweb.com/articulos/2033.php
Barbone, V. G. (Semtiembre/Octubre de 2017). Instituto de Ingeniería Eléctrica – Universidad de la República , Uruguay. Obtenido de Cursos Basicos De Linux: http://iie.fing.edu.uy/~vagonbar/unixbas/expreg.htm
Guido, S., & Sepulveda, M. A. (1998). LinuxFocus . Obtenido de Expresiones Regulares: http://www.linuxfocus.org/Castellano/July1998/article53.html
Lanero, A. V. (s.f.). Introducción a las Expresiones Regulares. Obtenido de Teoría de Autómatas y Lenguajes Formales: https://www.infor.uva.es/~mluisa/talf/docs/aula/A1.pdf