Expresiones regulares a partir del autómata finito equivalente: Parte I

¿Por qué esta magnífica tecnología científica, que ahorra trabajo y nos hace la vida más fácil, nos aporta tan poca felicidad? La repuesta es esta, simplemente: porque aún no hemos aprendido a usarla con tino.

Albert Einstein

En todas las ramas de la ingeniería, ciencia o economía existe la necesidad de resolver algún problema de optimización (control de sistema, optimización de recursos o producción, etc.) y se preguntarán ¿qué es optimizar? Sin duda, buscar la mejor manera de realizar una actividad.

Las Matemáticas lo enfocan en el estudio de los problemas o el proceso de encontrar los mínimos y máximos de una función.

En Economía es la forma neoclásica de la racionalidad, o sea, se trata de elegir la mejor opción entre distintas posibilidades.

En las Letras, optimizar sería lograr construcciones sintácticas y semánticas que hagan posible una comunicación más clara y efectiva entre emisores y receptores.

De ahí que la optimización se pueda definir como la minimización de algo malo, o la maximización de algo bueno.

En Informática, sería transformar un programa para que realice las mismas tareas en menos tiempo, con menos requerimientos de memoria y empleando los recursos de forma óptima. Siempre han existido(y existirán) situaciones que requieren la optimización para resolver un problema dado. En el caso de los informáticos, si con pocos códigos pudieran mejorar un software, ahorrarían tiempo y disminuiría el desgaste físico e intelectual.

Para el programador las expresiones regulares son muy útiles. Esta poderosa herramienta permite escribir códigos cortos y ahorrar tiempo, especialmente en JavaScript cuando no se cuenta con una conexión a Internet de alta velocidad. La mayor parte de la sintaxis de las expresiones regulares trabaja igual en una amplia variedad de herramientas y lenguajes de programación.

Por lo general, el significado de los símbolos utilizados para la construcción de una expresión, no tienen similitud con los del lenguaje natural o de programación, siendo la sintaxis para un inexperto difícil de recordar y bastante compleja. Una expresión regular tiene un autómata finito equivalente, o sea, al confeccionar un autómata finito podemos generar una cadena de texto (una vía más cómoda para inexpertos).

Habitualmente las expresiones regulares funcionan rápido, pero si se optimizan se logran mejores resultados.

Ejemplo:

• ;acdd|acdf|acdp|acd8
• ;acd(d|f|p|8)
• acd[dfp8]

Realizan la misma función. Al analizar sus longitudes 19, 12 y 9 respectivamente, la menor resulta más óptima, pues se logra una mayor potencia, rapidez y eficiencia al efectuar un filtrado, disminuyendo la longitud de la cadena de texto y manteniendo las mismas funciones.

Pero, ¿Qué tan importante es la optimización de expresiones regulares? En la programación web muchísimo, sobre todo si se dispone de un servidor con recursos limitados. De conseguirse que el código sea más eficiente, se dispondrá de más capacidad en el servidor (menos carga y mejor tiempo de respuesta).

De forma predeterminada, los motores de búsqueda de expresiones compilan una expresión regular en una secuencia de instrucciones internas (códigos de bajo nivel). Para mejorar el rendimiento, estos almacenan en caché todas las expresiones regulares de la memoria, evitando analizar cada vez que se utilice, una expresión en código de alto nivel. A fin de incrementar la eficiencia sería conveniente guardar en caché estas expresiones regulares minimizadas.

Al procesar una tabla con una cantidad de registros del orden de los millones en una base de datos de una aplicación, sería factible utilizar expresiones regulares pues resulta más costoso e impreciso usar en una consulta un operador como LIKE. De igual forma si se conecta un mayor número de usuarios, la simplificación de la expresión regular contribuiría a incrementar la velocidad en el procesamiento de los datos.

Este artículo es la introducción de una serie dedicada a expresiones regulares a partir de los autómatas.

Objetivos específicos:

Estudiar definiciones y algoritmos matemáticos para la optimización de autómatas finitos.

Realizar un estudio del estado del arte a un grupo de herramientas informáticas que tratan las expresiones regulares y los autómatas finitos.

Crear un algoritmo que realice la conversión de expresión regular a autómata finito.

Crear un algoritmo que realice la optimización de un autómata finito.

Validar la solución propuesta mediante experimentos.

Fundamento científico o marco teórico

Conceptos preliminares

La palabra conjunto se asocia con la idea de agrupar objetos iguales o diferentes, o sea, es una colección de elementos u objetos que guardan una relación entre sí. Un conjunto es una colección de objetos que cumplen una propiedad específica. Cada objeto del conjunto se llama elemento.

Existen diferentes tipos de conjuntos:

;Conjunto Vacío (f): Cuando ninguno de sus elementos cumple una condición dada.

Conjunto Unitario: Cuando contiene un solo elemento.

Conjunto finito: Cuando se puede contar la cantidad de elementos.

Conjunto infinito: Cuando no es finito.

Conjunto Universal: Contiene todos los elementos.

Conjunto potencia: Todos los subconjuntos de un conjunto A.

Subconjunto: Es una parte del conjunto y a la vez es un conjunto per se. Ejemplo: Sean los conjuntos A= {0, 1, 2, 3, 5, 6, 7, 8, 9} y B= {3, 4, 5}, en este caso decimos que B es subconjunto de A porque B está contenido en A.

Operaciones entre conjuntos:
Unión (∪): A∪B contiene los elementos de A y B. Ejemplo: A = {1, 2} y B = {2, 3, 4} siendo A∪B= {1,2,3, 4}. La unión de conjuntos es conmutativa y asociativa.

Intersección (∩): A∩B contiene los elementos que son iguales en A y B. Ejemplo: A= {1,2}y B= {2,3} siendo A∩B= {2}. La intersección es conmutativa y asociativa.

Diferencia (─): A−B contiene los elementos de A que no están en B. Ejemplo: A= {1, 2,3} y B= {2, 4,5} siendo A−B= {1,3}. La diferencia de conjuntos no es ni asociativa ni conmutativa.

Grafo: Estructura de datos. Un conjunto de objetos denominados nodos o vértices unidos por arcos. G(V,E) es un par ordenado, siendo V un conjunto de nodos o vértices y E, conjunto de arcos que relacionan a los nodos.

Optimizar: Buscar la mejor manera de realizar una actividad, según la Real Academia Española. En Informática, tratar de adaptar un programa o software que realice las mismas funciones o tareas en menos tiempo y requerimiento de memoria. Utilizar los recursos de forma rápida y eficiente.

Determinismo: No hay elección posible. Existe o no, una alternativa.

No Determinismo: Existen varias alternativas.

Símbolo: Tipo de abreviación de carácter científico o técnico; una representación de una información, como a, 6, +, etc. Un símbolo es una entidad indivisible.

Alfabeto: Conjunto no vacío de símbolos. Se utiliza generalmente la notación ∑ para representarlo.

El conjunto de cantidades u operaciones ordenadas donde cada una está determinada por las anteriores, es la definición de secuencias o cadenas de caracteres. Las mismas se forman con los símbolos de un alfabeto tales como casa, hola, a, etc. También son conocidas como palabras. Un caso particular es la palabra vacía,l, que no contiene ninguna letra.

La cantidad de letras o longitud de una palabra, se denota por |w|. Ejemplo, |adulto| = 6. Palabra nula o vacía l: su longitudes cero. Algunos autores utilizan e para denotarla.

La concatenación de dos o varias palabras origina la creación de palabras nuevas, cuya longitud es la sumatoria de las palabras originales. Ejemplo, si X = ciem, Y = piés, XY es la palabra ciempiés. Esta operación es asociativa, pero no conmutativa.

Un lenguaje es un conjunto de palabras y se pueden efectuar con ellas todas las operaciones de los conjuntos (unión, intersección, diferencia). La operación de concatenación de lenguajes, escrita como L1 • L2, resulta una extensión de la concatenación de palabras: L1 • L2 = {w|w = xy, x Î L1, y Î L2}.

Un lenguaje finito es aquel que contiene un número finito de palabras.

Un lenguaje infinito está determinado por la recursividad de sus requerimientos sintácticos simples.

Definición: Un lenguaje (L) es regular, si y sólo si se cumple al menos una de las condiciones siguientes:

;L, es finito.

;L, es la unión o la concatenación de otros lenguajes regulares R1 y R2, L = R1 U R2 o L = R1R2 respectivamente.

;L, es la estrella de Kleene de algún lenguaje regular, L = R*.

Teorema de Kleene: Un lenguaje es regular si y sólo si es aceptado por algún autómata finito.

Un lenguaje regular tiene su representación a través de una expresión regular.

FIN DE LA PARTE I

Referencias Bibliográficas

1. Pérez Martínez, Abel. ERAFPLN. 2009.

2. PÉREZ, NALLY CAMPO. INTRODUCCIÓN A LA TEORÍA DE CONJUNTOS. [En línea] http://www.e-socrates.org/mod/resource/view.php?id=4398.

3. REAL ACADEMIA ESPAÑOLA. [En línea] http://buscon.rae.es/draeI/.

4. Brena, Ramón.AUTOMATAS Y LENGUAJES. Monterrey : s.n., 2003.

5. Hopcroft, John E.Introducion to automata theory, languages, and computation. s.l. : Addison-Wesley, 2001.

6. Lawson, M. V. Finite automata. http://www.ma.hw.ac.uk/~markl/preprints/Lawson.pdf. [En línea]

7. RegExlib. [En línea] http://regexlib.com/default.aspx.

8. Javascript Regular Expression Validator. [En línea] http://tools.netshiftmedia.com/regexlibrary/.

9. RegexPal. [En línea] http://regexpal.com/.

10. metriplica.com, Grupo. ¡Prueba tus Expresiones Regulares! http://www.metriplica.com/4_4_herramientas.asp. 2008.

11. Regular Expression Tool. [En línea] http://erik.eae.net/playground/regexp/regexp.html.

12. Regexp Editor. [En línea] http://myregexp.com/.

13. Rad Software Regular Expression Designer 1.4.7528.27091. [En línea] http://www.radsoftware.com.au/?from=RegexDesigner.

14. Visual REGEXP 3,0. [En línea] http://www.softpedia.com/get/Programming/Other-Programming-Files/Visual-REGEXP.shtml.

15. Regulazy v1.0.3.0 (Beta). [En línea] http://tools.osherove.com/Default.aspx.

16. Regular Expression Workbench. [En línea] EricGu@Microsoft.Com.

17. Sells, Chris and Weinhardt, Michael.RegexDesigner v1.0.2727. [En línea] http://www.sellsbrothers.com/tools/.

18. Visual Automata Simulator. [En línea] http://www.cs.usfca.edu/~jbovet/.

19. Acosta, Francisco Ríos. SP-PS1. [En línea] http://www.friosa.com.mx.

20. RegexBuddy3. [En línea] http://www.regexbuddy.com/.

21. The Software Process Dashboard Initiative. [En línea] http://www.processdash.com/.

22. METODOLOGÍA DE MUESTREO. [En línea] http://www.hsa.es/id/investigacion/uai/uai_docs/muestreo/muestreo.htm.

23. Modelos Abstractos de Cómputo I. [En línea] http://www.sc.ehu.es/jiwnagom/MAC1/MAC-archivos/Tema2-parte3.pdf.

Libre de virus. www.avast.com