TeoLeng: [Ejercicio 4][Parte 1]

Buenas.

Tengo una duda sobre expresar las clases de equivalencia de Rm con expresiones regulares.

Ya habiendo minimizado el autómata finito determinista, no tengo ningún estado que pueda llegar al pozo, es necesario que lo agregue igualmente y de su expresión regular?

Lo agregué para que el autómata sea mínimo y completo entonces poder afirmar que las expresiones de las clases de equivalencia de Rm y RL son iguales, pero no consigo la expresión regular del estado que representa al estado pozo. No se si esto se debe a que no hay forma de llegar de los otros estados al pozo.

La ecuación que le corresponde al pozo me queda:

y2 = y2(0|1)

No logro entender como haría para aplicar Arden a esto.

Gracias.

Re: [Ejercicio 4][Parte 1]

de Santiago Gongora - lunes, 10 de abril de 2023, 11:40

Buen día,

cuando hablamos de "autómata completo" lo que estamos diciendo es que en todos los estados hay una transición definida para cada símbolo del alfabeto.
Es decir, que la función de transición esté definida completamente, y que no haya casos donde "no se sepa qué pasa".

Un pique rápido para chequearlo es el siguiente. Ponele que $\Sigma = \{a,b,c\}$ . Entonces deberías ir al estado $q_0$ y fijarte si hay una transición con a, otra con b y otra con c, que salgan de él. Luego vas al $q_1$ y lo mismo, luego al $q_2$ y lo mismo...y así para todos los estados del autómata. Si en todos los estados tenés transiciones con todos los símbolos del alfabeto, entonces es completo.

Volviendo a tu pregunta: si ya tenés definidas todas las transiciones del autómata, entonces es completo. Si es completo no tenés que agregar un pozo, porque lo único que vas a lograr es tener un estado "aislado" (es imposible llegar a él al reconocer una tira desde el estado inicial).

Fijate si con este hilo se te aclara un poco más: https://eva.fing.edu.uy/mod/forum/discuss.php?d=262958.

Cualquier cosa respondeme acá que la seguimos.

Saludos,
Santi

PD: Sobre lo de aplicarle Arden a $y_2 = y_2 (0|1)$ fijate la última sección de este documento. Vas a ver que el resultado tiene sentido con lo que me contaste, de que tu estado pozo "no le agrega nada al autómata".

Re: [Ejercicio 4][Parte 1]

de Diego Garat - lunes, 10 de abril de 2023, 11:55

hola:

simplemente agrego a lo que ya contestó santiago:

respecto a cómo resolver una ecuación de la forma X = X (0|1), se aplica el lema de arden, teniendo en cuenta que, en este caso, el término independiente es el vacío

r = (0+1)

s=vacío

=> la solución es s.r*, vacío.(0+1)* = vacío.

esto es análogo a lo que se muestra en el material complementario del lema de arden.

aquí la salvedad es que, por la forma de tu ecuación, deduzco que te faltan los autolazos en el estado pozo (y por ende tu autómata no es completo). al ser el automáta incompleto, esto no representa a la clase de equivalencia del estado pozo.

saludos,

d.-

Re: [Ejercicio 4][Parte 1]

de Diego Garat - lunes, 10 de abril de 2023, 12:50

hola:
no hagas caso a estas palabras, porque los lazos están ahí :)

"aquí la salvedad es que, por la forma de tu ecuación, deduzco que te faltan los autolazos en el estado pozo (y por ende tu autómata no es completo). al ser el automáta incompleto, esto no representa a la clase de equivalencia del estado pozo."

las que sí estarían faltando, son las correspondientes a las transiciones entrantes desde otros estados. si no hay ninguna, ese estado no tendría sentido (como dijo santiago) porque los automátas son conexos.

saludos,
d.-