Para obtener el AFND-transiciones vacías equivalente de la expresión regular se tienen en cuenta las tres operaciones básicas: concatenación, repetición y alternativas. El método utilizado lo describió por primera vez J. E. Thompson en su documento de 1968 del MCCA.
El AFND-e de una expresión regular se construye a partir del AFND parcial de cada subexpresión con una construcción diferente para cada operador básico. Después se unen estas subexpresiones con transiciones vacías. El AFND-e siempre contiene un estado inicial y otro final.
La expresión ab se divide en dos subexpresiones a y b. Este es un ejemplo simple de concatenación en el cual no aparecen las transiciones vacías. Aparecen cuando se utiliza el operador paréntesis:
La expresión a|b se divide también en dos subexpresionesa y b. El operador que la contiene indica que existe una alternativa. Apareciendo las transiciones vacías para unir estas dos expresiones:
La expresión regular a|b|c tiene dos formas de representar el autómata:
• Dividiendo esta expresión en tres subexpresiones a, b, c
• Dividiendo la expresión por primera vez, en dos subexpresionesa y b|c; después se divide b|c en dos subexpresiones b y c.
La expresión regular a?:
a*:
a+
Un ejemplo que se puede detallar y analizar sería el siguiente. Llamaremos a los pasos iteraciones:
Expresión regular: ad|ad*
En la Iteración 1: se divide la expresión en dos subexpresiones y se aplica la operación alternativa:
Iteración 2: se aplica la operación de concatenación a los nodos (q1, q3) y (q2, q4):
Iteración 3 y final: se aplica la operación de repetición a la subexpresión d* en el nodo (q7, q4), obteniendo el siguiente AFND-e equivalente:
Recomendacion: Leer:
Expresiones regulares a partir del autómata finito equivalente: Parte I
Expresiones regulares a partir del autómata finito equivalente: Parte II
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.
No hay comentarios:
Publicar un comentario