Buenas, estuve dando vueltas con este ejercicio y quería consultar. Me cuesta entender cómo construir un autómata que sea capaz de leer la tira desde el final.
Hasta ahora todo lo que pude hacer es un AFD con 3 estados qa ,qb ,qc donde cada uno representa el resultado actual de la multiplicación. Las transiciones son, según el estado en el que estoy, al estado que caigo considerando la operación con el simbolo que leo. Pero esto sería como hacer la asociativa de izquierda a derecha, que es lo opuesto a lo que quiero.
Agradezco la ayuda, saludos
hola:
efectivamente, la asociación de derecha a izquierda es más complicada... una posible idea es que cada estado pase de representar "lo que vas evaluando" a "lo que quiero que evalúe el resto".
por ejemplo, supongamos que estoy en el estado A (quiero que la tira evalúe en A), y leo la letra "c". ¿qué valor tiene que tener el resto de la tira z para que el resultado sea A? mirando la tabla, la única opción es c, ya que c.c = a. luego, g(A, c) = { C }.
¿qué sucede si en cambio en ese estado leo una a? z podría tomar dos valores, b o a, ya que a.a = a.b = a. luego, g(A,a) = {A, B }. (en realidad falta alguien, pero para que se entienda la idea, dejo esos dos estados).
último ejemplo, estoy en el estado B y viene una a. en este caso no hay posible valor de z que haga que a.z = b, luego g(B,a) = {}
efectivamente, la asociación de derecha a izquierda es más complicada... una posible idea es que cada estado pase de representar "lo que vas evaluando" a "lo que quiero que evalúe el resto".
por ejemplo, supongamos que estoy en el estado A (quiero que la tira evalúe en A), y leo la letra "c". ¿qué valor tiene que tener el resto de la tira z para que el resultado sea A? mirando la tabla, la única opción es c, ya que c.c = a. luego, g(A, c) = { C }.
¿qué sucede si en cambio en ese estado leo una a? z podría tomar dos valores, b o a, ya que a.a = a.b = a. luego, g(A,a) = {A, B }. (en realidad falta alguien, pero para que se entienda la idea, dejo esos dos estados).
último ejemplo, estoy en el estado B y viene una a. en este caso no hay posible valor de z que haga que a.z = b, luego g(B,a) = {}
¿cuando estoy seguro que algo evalúa en A, B o C? cuando la *última* letra es precisamente una a, b o c, respectivamente.
saludos,
d.-
d.-
Buenas, gracias por la respuesta. Creo haber podido modelar el autómata siguiendo tus indicaciones, el problema que me surge ahora es la decisión de los estados finales. El estado inicial, siguiendo tu nomenclatura lo puse como A, ya que dada una tira, quiero aquellas que evalúen "a" como resultado. Pero, al comenzar a computar una tira en el autómata me sucede que hay tiras válidas que terminan en en cualquiera de los estados A, B o C, así como también tiras inválidas que terminan en estos estados, con lo cual no me queda claro cómo definir el estado final.
Agradezco la ayuda, saludos
Agradezco la ayuda, saludos
En respuesta a Facundo Rodríguez Martínez
Re: [Ejercicio 2] [Parte b]
Me pasaba lo mismo, lo que hice fue poner una transicion desde los estados A, B y C hacia un estado final F, donde Delta(A,a) = F, Delta(B,b) = F y Delta(C,c) = F, dándole la opcion de terminar en ese punto, porque por ejemplo, si estás en el estado 'A', lo que querés es que la asociacion que viene despues (el resto de la tira) se evalue en 'a'. Pero si justo el resto de la tira es el simbolo final de esta, y digamos que te viene justo lo que querias que es algo que vale 'a' (en este caso el simbolo a), entonces le tenes que dar la opcion de terminar ahí y lo haces con esa nueva transicion (y en caso de que no termine ahi se va a un pozo para terminar de leer el resto de la tira). Al igual que vos puse el estado inicial como A, y el unico estado final seria ese F.
hola:
sí, esa es la idea. por eso les dije que faltaba "algo" en g(A,a), y que la condición era que la *última" letra era la del estado.
saludos,
d-
Clarísimo, gracias a los 2 por la ayuda :)