Consultas sobre el Práctico 3

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