Buenas gente.

La verdad no tengo mucha idea de cómo armar correctamente la expresión regular de un autómata ya que en nuestro curso (y como muchos más) nos dejaron a la deriva con este tema y la presentación de powerpoint tampoco me sirvió mucho. En el libro de la cátedra y en los ejercicios resueltos está explicado el método utilizado, pero la verdad es que no los acabo de entender y/o termino armando cualquier expresión.

Les dejo este ejercicio de final como ejemplo a ver si algún alma caritativa se detiene a explicarme como proceder paso por paso (sí, re pesado )

Sea la siguiente tabla de transición de un autómata finito:

d 0 1
-----
a b a
b b c
c c b

a es estado inicial, b es estado final. d es la función de transición.

Indique si alguna de las siguientes expresiones regulares corresponde al lenguaje reconocido por el autómata.

Desde ya, gracias.

"Indique si alguna de las siguientes expresiones regulares corresponde al lenguaje reconocido por el autómata."
Podés poner las expresiones que pone despues? para guiarme un poco, lo estoy tratando de sacar, de autómatas en clase vimos solo un ejemplo.

Se me piantó, qué gil .

Las expresiones son:

I) 1* 0 (1 0* 1 v 0*)*
II) 1* 0 0* (1 0* 1)*

la que corresponde es la primera.

Cómo hice yo? dibujé el autómata y seguí el caminito de 0 y 1 todavía no empecé a estudiar autómatas así que no conozco un "método", pero lo que yo hice fue seguir al autómata y ver que la primera expresión regular da todas las posibles entradas que el autómata reconoce como verdaderas, pero la segunda no.


El problema con la segunda es que el autómata PUEDE terminar en 0, ya que B es estado final y tiene un bucle con el 0, pero la expresión regular 1* 0 0* (1 0* 1)* admite terminar con 0 pero no admite terminar con 1010 por ejemplo.

A lo que voy, la expresión 1001010 es aceptada por el autómata, pero no por la expresión regular, por ende la segunda está mal.

Vallo tiene razón, en las respuestas dice que el 1 es el correcto, pero después sólo dice "(se puede probar usando el método)" xD
Despues de probar métodos hipoteticos con otros ejercicios resueltos de autómatas (punto 4, recuperatorio tema 08 y punto 4, examen final 16/12/09) hasta que alguno coincida con el resultado creo que ya entendí como es , hay que hacer esto:


a=1a v 0b
(estoy poniendo que si elijo 1 me voy a "a" y si elijo 0 me voy a b, el que va al mismo estado va primero, porque si salto al otro estado ya no puedo pasar por el bucle, lo mismo se hace con los demás, es casi como copiar el cuadro de transiciones. La que resuelve los finales pone + en vez de v, pero parece que a Peralta le gustan las v porque asi están en su libro y en los enunciados de los finales)
b=0b v 1c
c=0c v 1b


Tomo el primero:
a=1a v 0b
Como el 1 me lleva al mismo estado es bucle, así que quito esa a y le pongo un asteriosco al 1 (que quiere decir que se puede poner ninguna o infinitas veces)
a=1* v 0b
Como es necesario que pase por 0b para llegar al estado final, quitamos ese "v", ya que no es opcional.
a=1*0b

Para obtener la expresión regular el objetivo es reemplazar todo en la ecuación(?) del primer estado (a), todavía no sabemos cuanto es b, y para obtener la b tenemos que primero obtener la c, asi que vamos a trabajar ahora con la c.

c=0c v 1b
Como tenemos otro bucle: c= 0* v 1b
Y nos deshacemos de la v de nuevo porque es necesario pasar por 1b para ir al estado final.

Queda: c= 0*1b

Ahora reemplazamos eso en la de la b:

b=0b v 1c
b=0b v 1(0*1b)
b=0b v 10*1b
Sacamos factor comun b
b=(0 v 10*1)b

Como es la misma letra del estado, lo reemplazamos por el asterisco como ya habiamos hecho (ya que como nos llevan de regreso a b, podemos recorrer esas aristas cuantas veces queramos)

Queda b=(0 v 10*1)*

Ahora volvemos a la del primer estado y reemplazamos la b.
a=1*0b
a=1*0(0 v 10*1)*

Eso sería lo mismo que
a=1*0(10*1 v 0)*
En este caso se puede cambiar 0 v 10*1 por 10*1 v 0, pero si cambiaba el orden en la primera que hice(a=1a v 0b) y ponia 0b v 1a estaba mal ya que si tomo 0b no puedo volver y hacer 1a, en cambio en esta ultima, tanto 10*1 y 0 empiezan y terminan en b

Este me mató y no viene con respuesta....

Tenés que depurar la tabla del autómata (eliminar estados erróneos) y armar un sistema de ecuaciones. Aclaro que no lei todo el post y me acabo de despertar con insomnio T_T, ahora en un rato veo si me sale

la tabla es esta:

TT | 0 | 1
-------------
a-+| a | b
b+ | a | c
c |{c,b}| c

No tiene estados erróneos entonces no hay que depurarla.

Entonces nos uqeda:

a = 0a + 1b + Épsilon
b = 0a + 1c + Épsilon
c = 0c + 0b + 1c = (0 + 1)c + 0b

c = (0+1)*0b
b = 0a + 1(0+1)*0b y aca me quedé ya no se que hacer, alguien que se acuerde más de la cursada de sintaxis? xD

Consejo: Nunca empieces a resolver las ecuaciones con la ecuación del primer estado. Partí de las demás, y tratá de llegar a que te quede al final al ecuación del estado inicial.

Aclaro la notación que usé:

a- es un estado inicial, b+ denota un estado final, a-+ denota un estado inicial y final

+ significa lo mismo que v
épsilon vendria a ser lambda (la palabra vacía)

Por cierto, un amigo que también curso sintaxis logró armar la ER anirus, pero le quedó enorme. De dónde sacaste ese ejercicio??

(02-08-2010 22:48)Lean escribió:  Por cierto, un amigo que también curso sintaxis logró armar la ER anirus, pero le quedó enorme. De dónde sacaste ese ejercicio??

Del libro de Matemática Discreta de Peralta, es el punto iii, del ejercicio 39 de la página 397.

TT | 0 | 1
-------------
a-+| a | b
b+ | a | c
c |{c,b}| c

tenes a 0a + 1c +e
c= 0c + 0b + 1c

Siempre te conviene evitar el estado inicial, el resto podes mezclarlas como quieras. Y terminas la ER en el estado final.
arrancas por c=0c + 0b + 1c --> factor comun a derecha y queda c=(0+1)c + 0b
esto es la op estrella asique queda ---> c=(0+1)*0b
esto lo mandas a la ecuacion b=0a + 1c + e; reemplazas ahi y te queda
b=0a + 1(0+1)*0b + e
llevas el 1(0+1)*0b a la derecha, para poder aplicar op estrella; queda asi:
b=1(0+1)*0b + 0a + e; esto es operacion estrella nuevamente; asique aplicas y queda
b=(1(0+1)*0)*(0a + e) todo este choclo lo reemplazas en la 1º ecuacion a=0a + 1b +e

y queda a=0a + 1(1(0+1)*0)*(0a+e) + e ----> ahi "distribuis" el (0a + e) para separar el a y poder luego sacar factor comun;
a=0a + 1(1(0+1)*0)*0a + 1(1(0+1)*0) +e
y wooala, sale factor comun de "a" a derecha
a=(0 + 1(1(0+1)*0)*0)a + 1(1(0+1)*0)+e y tenemos al operador estrella una vez mas; lo aplicamos y tenemos la ER

a=(0 + 1(1(0+1)*0)*0)*(1(1(0+1)*0)+e)

ese choclo es una posible ER, hay varias jajaj

---

la forma esta bien hecha, aclaro que hice a veces copiar y pegar asique revisen que no me haya comido algun termino

(02-08-2010 23:06)gonnza escribió:  TT | 0 | 1
-------------
a-+| a | b
b+ | a | c
c |{c,b}| c

tenes a 0a + 1c +e
c= 0c + 0b + 1c

Siempre te conviene evitar el estado inicial, el resto podes mezclarlas como quieras. Y terminas la ER en el estado final.
arrancas por c=0c + 0b + 1c --> factor comun a derecha y queda c=(0+1)c + 0b
esto es la op estrella asique queda ---> c=(0+1)*0b
esto lo mandas a la ecuacion b=0a + 1c + e; reemplazas ahi y te queda
b=0a + 1(0+1)*0b + e
llevas el 1(0+1)*0b a la derecha, para poder aplicar op estrella; queda asi:
b=1(0+1)*0b + 0a + e; esto es operacion estrella nuevamente; asique aplicas y queda
b=(1(0+1)*0)*(0a + e) todo este choclo lo reemplazas en la 1º ecuacion a=0a + 1b +e

y queda a=0a + 1(1(0+1)*0)*(0a+e) + e ----> ahi "distribuis" el (0a + e) para separar el a y poder luego sacar factor comun;
a=0a + 1(1(0+1)*0)*0a + 1(1(0+1)*0) +e
y wooala, sale factor comun de "a" a derecha
a=(0 + 1(1(0+1)*0)*0)a + 1(1(0+1)*0)+e y tenemos al operador estrella una vez mas; lo aplicamos y tenemos la ER

a=(0 + 1(1(0+1)*0)*0)*(1(1(0+1)*0)+e)

ese choclo es una posible ER, hay varias jajaj

---

la forma esta bien hecha, aclaro que hice a veces copiar y pegar asique revisen que no me haya comido algun termino

Gracias , una pregunta, hay alguna regla sobre cuando quitar los + y concatenar? porque yo no estaba segura de cuando se podía hacer esto:
b=1(0+1)*0b + 0a + e
b=(1(0+1)*0)*(0a + e)

y de porqué la ER queda
a=(0 + 1(1(0+1)*0)*0)*(1(1(0+1)*0)+e)
en lugar de a=(0 + 1(1(0+1)*0)*0)* + 1(1(0+1)*0)+e

Cita:Gracias , una pregunta, hay alguna regla sobre cuando quitar los + y concatenar? porque yo no estaba segura de cuando se podía hacer esto:
b=1(0+1)*0b + 0a + e
b=(1(0+1)*0)*(0a + e)

emm si, hay una regla
Para hacerlo mas facil por notacion, suponete que 1(0+1)*0 es X e Y es (0a + e); es decir, X es lo que viene antes del caracter e Y es lo que viene despues del caracter

entonces
b=Xb+Y

checate que esta propiedad es SOLO SI TENES DE AMBOS LADOS EL MISMO CARACTER.
Es decir, fijate que de ambos lados tenes "b"
Te explico: esa es una ecuacion de una transicion de automata no ? esto quiere decir que tenes una transicion de etiquetada con "X" que te lleva a "b" y
despues Y puede ser una o varias transiciones que te lleven a distintos estados (fijate que en el original tenes 0a que el 0 te lleva a "a")
esta ecuacion se resuelve "quitando" el estado repetido, elevando a estrella todo lo q viene antes, y concatenando todo lo que viene despues:
es decir; si b=Xb + Y -----> b=X*Y
se eleva la "X" y se concatena la "y".
Esto es asi porque "implica" que aplicas la produccion X cuantas veces quieras (o ninguna) siempre regresas al mismo estado b (por eso el op*) y luego, una vez que elegiste Y te fuiste del estado b con cualquiera de las transiciones "Y" y no volves mas por eso esta concatenado a la derecha.

Tene en cuenta que el estado repetido tiene que estar repetido una vez nomas.
Te tiro un ejemplo
b=Ab + Cb + H + J
aca tenes que hacer factor comun "b" para que se repita una sola vez la "b"; pero aparte, este factor comun tiene que ser a derecha, para que te quede algo a la izqueirda que operar con *
entonces, si
b=Ab + Cb + H + J----------> b=(A+C)b + H +J
ahora que lo tenes a derecha aplicas la propiedad, operando con * y concatenando el resto y woala
b=(A+C)*(H+J) fijate que se concatena "todo el resto" como si fuera un unico caracter, asique si hay varios con "+" separados, los metes en parentesis