Búscalo aquí:

Convertidor de Expresiones Regulares hacia Autómata Finito

Los lenguajes regulares se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes, como por ejemplo en el lenguaje L={abc, abcabc, abcabcabc, …}. La regularidad de la palabra “abc” en el lenguaje L permite definir muchos otros lenguajes basados en la idea de repetir esquemas simples. Esta es la idea básica para formar los lenguajes regulares. Por otro lado, las expresiones regulares (ER) son simplemente fórmulas cuyo propósito es representar un lenguaje.


Al tratar de encontrar una expresión regular para un lenguaje dado, mientras más complejo sea el lenguaje es obvio que resulta más difícil encontrar por pura intuición dicha expresión regular. En estos casos puede ser conveniente trabajar en forma metódica.

Sin embargo, en este post trataremos acerca de la conversión de una expresión regular (ER) a su equivalente en autómata finito (AF), lo cual sirve para probar que un determinado lenguaje es regular. Para hacer la transformación gradual de ER a AFN se requiere utilizar alguna representación de los lenguajes regulares que sea intermedia entre las ER y los AFN. Una posible solución es el uso de las gráficas de transición, las cuales son esencialmente AFN en que las etiquetas de las flechas tienen expresiones regulares, en lugar de palabras. Algunas reglas del uso de estas gráficas de transición para el paso de ER a AFN se puede observar en el gráfico superior, para más información sobre el tema pueden consultar en (1).

Sobre este trabajo, realicé hace algunos años atrás un pequeño programa que logra convertir de ER hacia AF, el cual, recibe como parámetro de entrada una expresión regular parentizada construida en base a un alfabeto y un conjunto de operadores. El resultado obtenido es un AFN el cual se representa mediante un conjunto de estados. El convertidor de ER hacia AF es llamado AutoConvert y aún no realiza la conversión de ER complejas puesto que aún es un software de prueba que utiliza un algoritmo básico, por lo que se agradece la comprensión y tolerancia del caso, sin embargo, compartiré el código fuente con fines académicos para que sea mejorado. Una vista de AutoConvert se observa enm la siguiente imagen:



El programa para convertir una expresión regular en un autómata finito ha sido elaborado en C++ y pueden descargar el ejecutable desde AQUÍ, para comprender su funcionamiento pueden teclear el comando ayuda. El código fuente en C++ lo pueden descargar desde AQUÍ.

Espero les sea de utilidad y el código compartido sea mejorado y a su vez, también compartido, saludos.


(1) Ramon Brena, “Autómatas y Lenguajes. Un enfoque de diseño”. Tec de Monterrey, 2003.


Quieres leer más post como éste???...suscribete aquí!!!

29 comentarios:

  1. sta muy bueno el programa te felicito

    ResponderEliminar
  2. gracias por el aporte
    muy buen programa
    UTEM te ama..

    ResponderEliminar
  3. hola muy bueno tu programa pero fijate que el enlace del codigo fuente no funciona te agradeeria mucho que lo subieras ya que me dejaron hacer un proyecto similar gracias.

    ResponderEliminar
  4. muy interesante me gustaria estudiar tu codigo fuente pero no sirve tu link se te agradeceria si lo subieras de nuevo gracias y felicidades

    ResponderEliminar
  5. hola que tal me gustaria profundizar mas en esto, pero queria ver el codigo fuente y el enlace esta malo, podrias subirlo nuevamente, bueno de antemano muchas gracias Marcelo

    ResponderEliminar
  6. Acabo de habilitar el link del codigo fuente del convertidor de expresiones regulares en automata finito: AutoConvert, a pedido de todos los lectores.

    Espero que les sirva como base para construir algo más potente, saludos

    ResponderEliminar
  7. muchas gracias Jorge, aun no lo veo, pero espero que me ayude adios, nuevamente gracias, y muy bueno tu blog, cosas asi son necesarias en la red ADIOS

    ResponderEliminar
  8. muchas gracias Jorge, aun no lo veo, pero espero que me ayude adios,

    ResponderEliminar
  9. los enlaces estan malos, x favor corrigelos

    ResponderEliminar
  10. siguen malos los enlaces, te agradeceria los corrijas x favor. Gracias

    ResponderEliminar
  11. Listo!, las disculpas del caso por el el error del link, el link para la descarga del programa para convertir una expresión regular en un autómata finito elaborado en C++ esta en: http://miembros.seccperu.org/jcvalverde/codes/AutoConvert_exe.rar

    saludos

    ResponderEliminar
  12. Hola buen día es un gusto saludarte fíjate que necesito hacer un programa en C++ que como interfaz tenga el traza de un autómata que valide un correo electrónico que tenga la sub cadena .edu, pero no se función me puede hacer el trazo me podrías ayudar....

    ResponderEliminar
  13. Hola, existen varios IDE de C++ que pueden ayudarte en hacer la interfaz grafica de usuario, uno de ellos es el wXDevC++.

    Por otro lado puedes revisar el codigo fuente en Java que se presenta en este post: Simulador protocolos RIP y OSPF ahi se muestra como graficar y trabajar las trazas de un autómata de manera gráfica.

    ResponderEliminar
  14. Puedes explicar que es cada simbolo?

    El * esta claro.
    El +: Lo utilizas 1 o mas.. o como or logico
    El "." No se para que es.

    Para que es la tirulilla? Gracias

    ResponderEliminar
  15. disculpa, no logro correr el programa, puedes explicare

    mi correor es :ponc_g022@hotmail.com

    ResponderEliminar
  16. disculpa pero los links no sirven, porfa podrias subirlos de nuevo.de antemano gracias.

    ResponderEliminar
  17. sip porfa me mandas el link o el codigo a mi correo mrcaesar1@hotmail.com

    ResponderEliminar
  18. Alguien tiene el codigo??? vuelvanlo a subir :D

    ResponderEliminar
  19. porfavor puedes mandarme el codigo a mi correo por favor es: wings.marcus@gmail.com

    ResponderEliminar
  20. no sirven los links... alguien tiene el código???

    ResponderEliminar
    Respuestas
    1. Disculpa, en estos momentos el servidor esta con fallas y no hay otras fuentes.
      Saludos

      Eliminar
  21. alguien tendra el codigo fuente?

    ResponderEliminar
  22. no puedo bajar el codigo fuente
    me lo podrian enviar
    alguien q ya lo tenga
    jesus_007delcid@hotmail.com

    ResponderEliminar
  23. ¿No tendrás el código del programa? Por favor responde.

    ResponderEliminar
  24. No funcionan los links, me puedes ayudar con el codigo fuente, mi correo es jsanabria1010@gmail.com. Gracias

    ResponderEliminar
  25. Buenas noches, me podria enviar el codigo en c++
    al correo: edu.david2706@gmail.com

    ResponderEliminar
  26. Me puedes compartir tu código al correo konantu@gmail.com

    ResponderEliminar
  27. Me compartirías tu código al correo, juan_8007@hotmail.com Gracias

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...