Seguimos buscando a Arshak. Ayudanos compartiendo!
Encuesta no oficial de docentes
Resultados de la encuesta no oficial de docentes
Probaste el SIGA Helper?

Donar $100 Donar $200 Donar $500 Donar mensualmente


Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
Final Julio 2019 - Duda con el ejercicio de regex
Autor Mensaje
Apellidocomplicado Sin conexión
Militante
Sin estado :(
***

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 85
Agradecimientos dados: 28
Agradecimientos: 38 en 15 posts
Registro en: Sep 2015
Mensaje: #1
Final Julio 2019 - Duda con el ejercicio de regex Dudas y recomendaciones Sintaxis y Semántica de los Lenguajes
En el final del 15/07/2019, el ej 1 dice
Cita: Dada la regex [ab]? dibuje el AF obtenido mediante Thompson

Una resolución correcta propuesta por el docente es
   

Según regexr, la expresión se explica de la siguiente forma.
   

El problema es que no entiendo por qué agregan tantas transiciones con nulo. ¿Por qué no hay menos? ¿Por qué no hay más? ¿Tiene que ver con que son dos caracteres?

Además, faltaría una rama donde reciba una a y una b seguidas, combinación que Regexr toma como válida.
Otros adjuntos en este tema
.png  Paso1.png ( 6,16 KB / 143) por manoooooh
.png  Paso2.png ( 12,75 KB / 140) por manoooooh
.png  Paso3.png ( 14,48 KB / 143) por manoooooh
(Este mensaje fue modificado por última vez en: 24-11-2019 18:16 por Apellidocomplicado.)
24-11-2019 17:52
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
manoooooh Sin conexión
Secretario de la SAE

******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 439
Agradecimientos dados: 0
Agradecimientos: 328 en 171 posts
Registro en: Feb 2017
Mensaje: #2
RE: Final Julio 2019 - Duda con el ejercicio de regex
Hola

(24-11-2019 17:52)Apellidocomplicado escribió:  
Cita: Dada la regex [ab]? dibuje el AF obtenido mediante Thompson

Esa regex equivale a la ER \(a+b+\varepsilon=(a+b)+\varepsilon\). ¿Ves por qué?

(24-11-2019 17:52)Apellidocomplicado escribió:  El problema es que no entiendo por qué agregan tantas transiciones con nulo. ¿Por qué no hay menos? ¿Por qué no hay más? ¿Tiene que ver con que son dos caracteres?

Tiene que ver con el algoritmo de Thompson.

Unión según Thompson:
  1. Construir dos AF básicos.
  2. Los dos EI dejan de serlo.
    • Se agrega un EI.
    • Se agrega una transición \(\varepsilon\) del EI a los EX-EI.
  3. Los dos EA dejan de serlo.
    • Se agrega un EA y dos transiciones \(\varepsilon\) de los EX-EA al nuevo EA.

Ejemplo: Queremos construir el AF según Thompson de la ER \(a+b\).

El paso 1 es:

   

El paso 2 es:

   

El último paso es:

   

De forma similar usamos el algoritmo para graficar \((a+b)+\varepsilon\), podemos llamar \(c=a+b\) para tener \(c+\varepsilon\) y usar la unión como operador binario, y siguiendo los mismos pasos se obtiene el AF de tu profesor.

(24-11-2019 17:52)Apellidocomplicado escribió:  Además, faltaría una rama donde reciba una a y una b seguidas, combinación que Regexr toma como válida.

¿Decís \(ab\)? Pero eso no forma parte de la regex original porque en ningún lado aparece el operador concatenación. A menos que haya cambiado algo la sintaxis de las regex, \([ab]\text{?}\) equivale a \((a+b)+\varepsilon\).

Saludos.
24-11-2019 19:18
Envíale un email Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] manoooooh recibio 2 Gracias por este post
Apellidocomplicado (28-11-2019), patriciojgf (16-12-2019)
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)