Parciales

Buenas tardes Matías.

 

Respuesta corta: el ejercicio pedía la cantidad de clases de equivalencia según $R_M$ de un autómata finito determinista válido ($M$ ), y no la cantidad de clases de equivalencia según $R_{M'}$  del autómata mínimo ($M'$ ). La diferencia en la cantidad que ven, al comparar su solución con la del parcial, viene de ahí.

Repuesta larga:  El error que ustedes tuvieron en esa solución es más bien conceptual, y tiene que ver con cómo se define la relación $R_M$. 

La relación $R_M$ determina que las tiras $x \in \Sigma^*$  e  $y \in \Sigma^*$ están relacionadas si, al ingresarlas en el autómata $M$, ambas terminan su ejecución en el mismo estado. Por lo tanto, la cantidad de clases de equivalencia definidas por $R_M$ es, exactamente, la cantidad de estados del autómata (incluyendo al pozo): no hay más opciones para clasificar esas tiras que la cantidad de estados disponibles. Es importantísimo que tengan en cuenta que esta definición es extremadamente dependiente del autómata $M$ en cuestión, porque para saber si $x \in \Sigma^*$  e  $y \in \Sigma^*$ están relacionadas se usa la función de transición de ese autómata.

Según entiendo, ustedes intentaron minimizar el autómata para hallar la cantidad de clases de $R_M$. Eso es incorrecto conceptualmente, porque lo que hallaron ahí no es la cantidad de clases de equivalencia según $R_M$, sino según $R_{M'}$, donde $M'$ es un autómata mínimo tal que $L(M) = L(M')$. Es por eso que la cantidad de clases de equivalencia les da diferente: en la solución del curso  el autómata en cuestión no está minimizado y en la solución de ustedes, sí.  En todo caso, no es que su solución esté mal, ya que sigue siendo un autómata finito determinista que acepta el mismo lenguaje que el autómata original... pero lamentablemente laburaron más de lo que pedía el ejercicio :/

 

Lo más importante - conceptualmente - de todo esto es que: la relación $R_M$ se define independientemente de si el autómata $M$ en cuestión es el mínimo, o no. Otro tema aparte (y quizás la confusión que tuvieron es por esto) es que, si ese autómata es mínimo, entonces las clases de $R_M$ de ese autómata $M$ coinciden con las clases definidas por $R_L$, donde $L$ es el lenguaje aceptado por el autómata mínimo $M$. Ese resultado teórico es el que se usa para argumentar la solución del siguiente ejercicio de ese parcial.

 

Espero que esto aclare un poco la confusión y ya saben que, cualquier duda, a las órdenes por acá (o en la clase de consulta de este jueves 24 de mayo).

Saludos,
Santi