UTNianos

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
[attachment=18452]

Según regexr, la expresión se explica de la siguiente forma.
[attachment=18453]

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.

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.