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

Autor: Ing. Yeiniel Alfonso Martínez

e-mail: sitieh2013@gmail.com 

Expresiones Regulares. 

Una expresión regular es una cadena de texto para describir un patrón de búsqueda. Es una fórmula que caracteriza un lenguaje ─un conjunto de cadenas. Resultan útiles en compilación y desarrollo del Procesamiento de Lenguaje Natural. También permiten sustituir textos, editar o generar nuevos ficheros, manipulando el contenido de otros.  Las expresiones regulares son convenientes, rápidas y potentes al efectuar un filtrado sobre un caso dado, y lograr un resultado más reducido y específico. Usan poca memoria y ahorran códigos. Importante en JavaScript, para conexiones lentas en Internet. 

Las siguientes definiciones son tomadas del libro Autómatas y Lenguajes (3) 

Definición: Sea ∑ un alfabeto. El conjunto ER de las expresiones regulares contiene las cadenas en el alfabeto ∑ U {λ, |, •, *, (,), Ø} que cumplen con lo siguiente:

Las plataformas de desarrollo disponen de expresiones regulares, aunque cada una usa su propio dialecto. Las expresiones regulares se basan en sus operadores básicos (* + | () ?), Comodines (\w \s \d) y en las tres operaciones básicas: concatenación, repetición y alternativas.

Operadores Básicos: 

• Ninguna o más repeticiones (*): a* indica que acepta ninguna o más repeticiones de a. 
• Una o más repeticiones (+): a+ indica que acepta una o más repeticiones de a.
• Opcionalidad  (?): a? indica que a puede aparecer o no. De aparecer, sólo una vez.
• O lógico (|): a|b indica que existe una alternativa que puede aceptar a o b. 
• Agrupación ( ): Este operador, los paréntesis, se utiliza cuando se desea agrupar una parte de la expresión para un tratamiento especial. Ejemplo: (a|b)?c, tiene las combinaciones de texto siguiente: ac, bc, c. debido a que la subexpresión a|b se encuentra entre paréntesis, se le aplica el operador opcional ?. Si esta subexpresión no estuviera agrupada a|b?c los textos serían: a, c, bc, porque dicho operador se le aplica sólo a la b. 

Existen otros metasímbolos: 

•  Cualquier caracter (.): .a. indica que cualquier cadena de longitud 3 contiene la letra a en la posición del centro. 
• Clase de caracteres [ ]: [0-9] indica cualquier carácter entre el cero y el nueve. 

Comodines y abreviaturas: 

•  \w: indica los alfanuméricos. ([A-Za-z_0-9]) 
• \s: indica los caracteres de separación (\t ,\n, \r y espacio). 
• \d: indica los dígitos.

Teorema: Todo lenguaje definido por una expresión regular también es definido por un autómata finito (5).

Autómatas finitos 

En el artículo de M. V. Lawson (6) el término autómatas finitos describe una clase de modelos de computación que se caracterizan por tener un número finito de estados. Son dispositivos informáticos que aceptan o reconocen los idiomas regulares.

Según R. Brena (4), un autómata finito es el modelo matemático de un sistema. El mismo recibe una cadena constituida por símbolos de un alfabeto, y determina si esa cadena pertenece al lenguaje que él reconoce.

La definición formal de J.E. Hopcroft (5) plantea lo siguiente:

El diagrama de transición determina las cadenas del lenguaje a través de un grafo dirigido con información añadida. Los nodos del grafo representan los estados del autómata finito y señalan hasta donde se analizó la cadena. El estado inicial (s) o comienzo del autómata es marcado con una flecha; los estados finales o aceptación (F) por un doble círculo. Las etiquetas de los arcos están definidas por los símbolos del alfabeto. Cuando una cadena termina en un estado final es aceptada por el lenguaje.

La palabra “ami’ en francés, significa “amigo” en español. Se puede notar que tienen cierta similitud, “ami” es un subconjunto de “amigo”, A = {a, m, i}, B = {a, m, i, g, o},  A∪B= {a, m, i, g, o}; la expresión regular amigo|amio ami(go)? reconocen esta palabra en los idiomas mencionados. El autómata que lo representa se muestra en la Figura, donde q1 es el estado inicial o inicio, q4 y q7 son los estados aceptados o finales. Al llegar al estado q4 se obtiene la palabra “ami”, y en q7 “amigo”.

Si se le añaden las palabras en plural hay que agregar un estado. El autómata cambia transformando la expresión regular en amigos|amis|amigo|ami o ami(go)?(s)?

Otra forma de representar un autómata es mediante Las Tablas de Transiciones: Las filas muestran los estados del autómata finito, y las columnas los símbolos del alfabeto. Las intersecciones de fila y columna muestran el próximo estado, la Tabla 1.1 muestra un ejemplo de tabla de transiciones del autómata finito de la Figura anterior.

Los autómatas finitos pueden ser no deterministas o deterministas, existiendo tres clasificaciones: AFND-e, AFND y AFD.

A través de los autómatas finitos deterministas (AFD) se pueden generar las expresiones regulares y viceversa.

La expresión regular ad*|ad|ad+ no es óptima al contener elementos redundantes (|ad|ad+). Esta se puede transformar en un AFD a través de un modelo matemático, y minimizarlo para obtener una nueva expresión regular equivalente o igual a la anterior. Estos dos resultados se pueden comparar y escoger el más eficiente y optimizado. En este ejemplo la expresión resultante sería ad* siendo la más óptima porque realiza las mismas funciones que la anterior y su longitud es menor.

Existen cuatro notaciones diferentes de equivalencia para expresiones regulares(4):

Definición: Dos autómatas A1 y A2 son equivalentes, cuando aceptan el mismo lenguaje.

FIN DE LA PARTE II

Recomendacion: Leer Expresiones regulares a partir del autómata finito equivalente: 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/OtherProgramming-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.