Como corroborar una ER hallada con el metodo de clases de equivalencia

Como corroborar una ER hallada con el metodo de clases de equivalencia

de Lourdes Alejandra Couto Burgos -
Número de respuestas: 1

Buenas, 

No me quedo claro como corroborar que la ER que encontré con el método de clases de equivalencia es correcta. 

Se que la ER es el pipe de todos los Xf, pero como seria la forma de corroborarla con el autómata (mirándolo)? 

Porque se que, en el kleene, es verificar las tiras que entran en el estado inicial y llegan al estado final. Pero no me queda muy claro en el de equivalencia. 

Lo estaba pensando de la siguiente forma: me paraba en cualquier nodo, y me fijaba las "opciones" de tiras con la cual llegar a los finales, pero no se si es correcta esa idea. 

Gracias!! 

En respuesta a Lourdes Alejandra Couto Burgos

Re: Como corroborar una ER hallada con el metodo de clases de equivalencia

de Santiago Gongora -

Buen día,

el método de clases de equivalencias se presta bastante para ir chequeando las E.R. a ojo a medida que se van hallando.

Cada X_i representa "¿Qué forma tienen las tiras que llegaron a q_i ?", entonces podemos simplemente pararnos en cada estado y ver (a ojo) si el patrón descrito por la expresión regular coincide con el de las tiras que llegan a ese estado. Por poner un ejemplo rápido, si estamos viendo este pedacito de autómata:

entonces una expresión tipo X_1= b | a sabemos que es incorrecta, porque no hay forma de llegar a q_1 con una "a". Una expresión con mejor pinta sería por ejemplo: X_1 = b | b.(a|b) ^* .  

Después chequearíamos (exactamente de la misma forma) si tienen sentido las expresiones de  X_2, X_3,... . En general vas a ver que, por la forma en que se arman las expresiones, este chequeo no lo hacés enteramente cada vez: las expresiones dependen entre sí, entonces los "cachos de expresión" que ya chequeaste no los tenés que volver a chequear. Ponele, si en el ejemplo de arriba se continuara con que X_2 = X_1 a , toda la expresión asociada a X_1 ya la habrías chequeado, entonces no tendrías que hacerlo de vuelta.


Todo esto que te digo es desde el punto de vista práctico, para ver si estás ejecutando bien el método. Desde un punto de vista teórico se podrían usar las pruebas por inducción que demuestran que una E.R. genera un lenguaje dado.

Cualquier cosa la seguimos,
Santi