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

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

de Diego Garat -
Número de respuestas: 0

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.-