[2017] [Primer Parcial] [Ejercicio 2] [Parte iv]

[2017] [Primer Parcial] [Ejercicio 2] [Parte iv]

de Juan Martin Nuñez Pena -
Número de respuestas: 1

Buenas.

Mi duda es sobre como se calculan o se ven las cantidades de clases de equivalencia en casos como estos en los que no tenemos el AFD minimo y completo. Aparece varias veces esta pregunta de cantidades de clases de equivalencia pero no termino de entender como calcularlas o estimarlas. No solo en ejercicios como este que me pide comparar la cantidad de dos lenguajes distintos, sino tambien en otros que pide decir si es verdadero o falso si el lenguaje tiene mas de X clases de eq.

Gracias.


En respuesta a Juan Martin Nuñez Pena

Re: 1er Parcial 2017-Ejercicio 2-Parte iv

de Diego Garat -

hola:

si la pregunta es sobre RM, esto es muy sencillo: la cantidad de clases es igual a la cantidad de estados que tenga el autómata M. hay que tener en cuenta que, para que la relación esté bien definida,  el autómata M tiene que ser determinista y completo, pero no necesariamente mínimo. además, tenemos un algoritmo para el cálculo de las clases de equivalencia de RM (sistema de ecuaciones).

si la pregunta es sobre RL, lo primero que sabemos es que la cantidad va a ser a) finita, si el lenguaje es regular y b) infinita, si el lenguaje no lo es. esto se desprende del teorema de Myhill-Nerode, con otra conclusión interesante: para el caso de un lenguaje regular, la cantidad y clases definidas por la RN es igual a las definidas por RL. calcular las clases de equivalencia definidas por RL equivale a calcular las clases definidas por RN, siendo N el autómata mínimo que reconoce a un lenguaje L.

con estas herramientas conceptuales, se pueden normalmente contestar todas las preguntas. en el ejercicio que planteás, Lb es un lenguaje regular mientras que La no lo es. luego, RLa define infinitas clases de equivalencia mientras que RLb define una cantidad finita de clases. luego, la afirmación es verdadera.

si te piden calcular las clases definidas por RL, y L es regular, podés obtener el autómata, minimizarlo y calcular las clases de su autómata mínimo. lo mismo aplica para la cantidad de clases de RL: teniendo el AFD mínimo, será la misma que la de RM y, por ende, la cantidad de estados de ese autómata.

saludos,

d.-