Donar $20 Donar $50 Donar $100 Donar mensualmente
 


Enviar respuesta 
 
Calificación:
  • 2 votos - 5 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[Discreta] Expresión regular del Autómata
Autor Mensaje
NathanDrake Sin conexión
Profesor del Modulo A
...
*****

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 399
Agradecimientos dados: 16
Agradecimientos: 79 en 23 posts
Registro en: Apr 2010
Mensaje: #1
[Discreta] Expresión regular del Autómata Dudas y recomendaciones Matemática Discreta
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 =P)

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.
28-07-2010 17:33
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.163
Agradecimientos dados: 77
Agradecimientos: 194 en 69 posts
Registro en: Nov 2009
Mensaje: #2
RE: [Discreta] Expresión regular del Autómata
"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.
(Este mensaje fue modificado por última vez en: 28-07-2010 18:18 por Anirus.)
28-07-2010 18:05
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
NathanDrake Sin conexión
Profesor del Modulo A
...
*****

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 399
Agradecimientos dados: 16
Agradecimientos: 79 en 23 posts
Registro en: Apr 2010
Mensaje: #3
RE: [Discreta] Expresión regular del Autómata
Se me piantó, qué gil =P.

Las expresiones son:

I) 1* 0 (1 0* 1 v 0*)*
II) 1* 0 0* (1 0* 1)*
28-07-2010 18:35
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Vallo Sin conexión
Mejor Firma 2011
HAHAHAHAH

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.709
Agradecimientos dados: 142
Agradecimientos: 81 en 64 posts
Registro en: Sep 2009
Mensaje: #4
RE: [Discreta] Expresión regular del Autómata
la que corresponde es la primera.

Cómo hice yo? dibujé el autómata y seguí el caminito de 0 y 1 =P 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.
28-07-2010 18:49
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.163
Agradecimientos dados: 77
Agradecimientos: 194 en 69 posts
Registro en: Nov 2009
Mensaje: #5
RE: [Discreta] Expresión regular del Autómata
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 =P, hay que hacer esto:

[Imagen: autom.jpg]
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 mensaje fue modificado por última vez en: 28-07-2010 20:37 por Anirus.)
28-07-2010 20:11
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.163
Agradecimientos dados: 77
Agradecimientos: 194 en 69 posts
Registro en: Nov 2009
Mensaje: #6
RE: [Discreta] Expresión regular del Autómata
Este me mató unsure y no viene con respuesta....
[Imagen: automata.jpg]
02-08-2010 00:27
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #7
RE: [Discreta] Expresión regular del Autómata
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

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
(Este mensaje fue modificado por última vez en: 02-08-2010 07:37 por Lean.)
02-08-2010 07:14
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #8
RE: [Discreta] Expresión regular del Autómata
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)

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
02-08-2010 10:18
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #9
RE: [Discreta] Expresión regular del Autómata
Por cierto, un amigo que también curso sintaxis logró armar la ER anirus, pero le quedó enorme. De dónde sacaste ese ejercicio??

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
02-08-2010 22:48
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.163
Agradecimientos dados: 77
Agradecimientos: 194 en 69 posts
Registro en: Nov 2009
Mensaje: #10
RE: [Discreta] Expresión regular del Autómata
(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.
02-08-2010 22:53
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #11
RE: [Discreta] Expresión regular del Autómata
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 =P 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 =P asique revisen que no me haya comido algun termino =)

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 02-08-2010 23:07 por gonnza.)
02-08-2010 23:06
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.163
Agradecimientos dados: 77
Agradecimientos: 194 en 69 posts
Registro en: Nov 2009
Mensaje: #12
RE: [Discreta] Expresión regular del Autómata
(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 =P 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 =P asique revisen que no me haya comido algun termino =)

Gracias =D, 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
03-08-2010 14:49
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #13
RE: [Discreta] Expresión regular del Autómata
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 =P 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 =P
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 thumbup3

[Imagen: v34BEFt.gif]
03-08-2010 15:05
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)



    This forum uses Lukasz Tkacz MyBB addons.