Donar $20 Donar $50 Donar $100 Donar mensualmente
 


Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[AYUDA] Ejercicio de Gramatica y Automatas Finitos
Autor Mensaje
mantovani.leandro Sin conexión
Empleado de Fotocopiadora
Las despedidas son esos dolore...
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 31
Agradecimientos dados: 1
Agradecimientos: 2 en 2 posts
Registro en: Dec 2013
Mensaje: #1
[AYUDA] Ejercicio de Gramatica y Automatas Finitos Ejercicios Matemática Discreta
Buenas tardes, si me pudieran dar una mano con este ejercicio se los agradeceria mucho. Estoy preparando el parcial de discreta y rindo en dos dias. Saludos!

[Imagen: thump_8728895ejercicio-automata.jpg]
Otros adjuntos en este tema
.png  automata parcial.png ( 15,24 KB / 1379) por rihardmarius

Un pesimista es un optimista con experiencia
(Este mensaje fue modificado por última vez en: 09-12-2013 11:09 por mantovani.leandro.)
09-12-2013 11:06
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
alvar Sin conexión
Secretario de la SAE
:D
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 629
Agradecimientos dados: 39
Agradecimientos: 35 en 29 posts
Registro en: Feb 2012
Mensaje: #2
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
Yo estoy en las mismas. Tiene gramatica tipo 2, por lo tanto no es posible obtener automata finito

Spoiler: Mostrar
[Imagen: Hamster-shot-plays-dead.gif]
09-12-2013 11:27
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
mantovani.leandro Sin conexión
Empleado de Fotocopiadora
Las despedidas son esos dolore...
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 31
Agradecimientos dados: 1
Agradecimientos: 2 en 2 posts
Registro en: Dec 2013
Mensaje: #3
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
Como llegaste a la conclusión de que tiene una gramatica del tipo 2 ? eso es lo que no me termina de quedar claro tampoco...

Un pesimista es un optimista con experiencia
09-12-2013 11:37
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
alvar Sin conexión
Secretario de la SAE
:D
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 629
Agradecimientos dados: 39
Agradecimientos: 35 en 29 posts
Registro en: Feb 2012
Mensaje: #4
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
Tipo 2 y 3 ambos tienen en lado izquierdo un no terminal, en el derecho es donde se diferencian, hasta donde se es que en el dalo derecho tiene que terminar con un Vt (terminal).

Vn---->Vn.Vt l Vt (ese seria un tipo 3)

Vn ---->Vt.Vn (ese seria un tipo 2)

Es hasta donde yo se, seguramente es asi porque yo lo hice en el parcial creyendo que era un tipo 3 y hice el automata. pero me la dieron como equivocada porque era del tipo2 =(. Si hubiera tenido claro ese concepto hubiera aprobado =D

Spoiler: Mostrar
[Imagen: Hamster-shot-plays-dead.gif]
09-12-2013 11:50
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
rihardmarius Sin conexión
Secretario de la SAE
Por qué no me derivas el loga...
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 415
Agradecimientos dados: 100
Agradecimientos: 378 en 66 posts
Registro en: Oct 2011
Mensaje: #5
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
es tipo 2 porque hay dos no terminales en el lado derecho, con tipo 3 solo puede haber un solo Vn

el lenguaje generado es: (ab)*acc*ba

yo hice el automata y me saque 10, asi q se podia hacer


Archivo(s) adjuntos Imagen(es)
   

(Este mensaje fue modificado por última vez en: 09-12-2013 12:16 por rihardmarius.)
09-12-2013 12:05
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
alvar Sin conexión
Secretario de la SAE
:D
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 629
Agradecimientos dados: 39
Agradecimientos: 35 en 29 posts
Registro en: Feb 2012
Mensaje: #6
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
(09-12-2013 12:05)rihardmarius escribió:  es tipo 2 porque hay dos no terminales en el lado derecho, con tipo 3 solo puede haber un solo Vn

el lenguaje generado es: (ab)*acc*ba

yo hice el automata y me saque 10, asi q se podia hacer

tengo entendido que solo se puede hacer un automata finito de una gramatica tipo 3. En este caso es tipo 2. si se puede hacer un automata pero no seria finito, seria automata pila (que no se ve en discreta).


YO HICE EL AUTOMATA TAL COMO LO HICISTE

Spoiler: Mostrar
[Imagen: Hamster-shot-plays-dead.gif]
(Este mensaje fue modificado por última vez en: 09-12-2013 12:21 por alvar.)
09-12-2013 12:13
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
mantovani.leandro Sin conexión
Empleado de Fotocopiadora
Las despedidas son esos dolore...
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 31
Agradecimientos dados: 1
Agradecimientos: 2 en 2 posts
Registro en: Dec 2013
Mensaje: #7
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
Si yo tenia en entendido eso tambien. Que el automata finito se podia hacer con una gramatica del tipo 3 nada mas... Gracias por la respuesta !

Un pesimista es un optimista con experiencia
09-12-2013 12:29
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
rihardmarius Sin conexión
Secretario de la SAE
Por qué no me derivas el loga...
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 415
Agradecimientos dados: 100
Agradecimientos: 378 en 66 posts
Registro en: Oct 2011
Mensaje: #8
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
entonces hice un automata de pila

como la gramatica es tipo 2, el lenguaje es tipo 2

(Este mensaje fue modificado por última vez en: 09-12-2013 16:54 por rihardmarius.)
09-12-2013 12:29
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
m68540534 Sin conexión
Profesor del Modulo A
3++ || 4--
*****

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 259
Agradecimientos dados: 246
Agradecimientos: 166 en 68 posts
Registro en: Mar 2013
Mensaje: #9
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
La gramática es de tipo 2 pero existe una gramática equivalente de tipo 3, equivalente significa que generan el mismo lenguaje. Básicamente te das cuenta al sacar la expresión regular del lenguaje, se puede ver como puso rihardmarius que existe expresión regular, no todos los lenguajes tienen. Un ejemplo es el lenguaje a^n º b^n, no existe expresión regular porque no hay forma de asegurar usando solo los * que las dos letras se repitan la misma cantidad de veces.
Todo lenguaje que pueda ser expresado por una expresión regular es un lenguaje regular, o sea de tipo 3, o sea generado por una gramática tipo 3, por eso se puede hacer el autómata, y es finito, el de pila es otra cosa que ni vimos.

Saludos!

Compilado para aprobar la cursada de Matemática Discreta - http://www.utnianos.com.ar/foro/tema-lib...-parciales
09-12-2013 17:13
Envíale un email Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] m68540534 recibio 1 Gracias por este post
Imakuni (09-12-2013)
mantovani.leandro Sin conexión
Empleado de Fotocopiadora
Las despedidas son esos dolore...
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 31
Agradecimientos dados: 1
Agradecimientos: 2 en 2 posts
Registro en: Dec 2013
Mensaje: #10
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
Osea que un lenguaje tipo 3 es generado por una gramática del tipo 3 y también por gramáticas que pueden ser equivalentes (como en este caso que la gramática es del tipo 2) ?

Un pesimista es un optimista con experiencia
09-12-2013 17:19
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
rihardmarius Sin conexión
Secretario de la SAE
Por qué no me derivas el loga...
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 415
Agradecimientos dados: 100
Agradecimientos: 378 en 66 posts
Registro en: Oct 2011
Mensaje: #11
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
tiene razon nuestro amigo m685

pasa q las de tipo 3 estan incluidas en las de tipo 2, (y tipo 2 en tipo 1 y asi) por eso siempre se puede sacar una gramatica tipo 2 a partir de una de tipo 3

en este caso se dio la casualidad de que inferimos una de tipo 3 a partir de una de tipo 2, q loco no?

09-12-2013 17:21
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
mantovani.leandro Sin conexión
Empleado de Fotocopiadora
Las despedidas son esos dolore...
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 31
Agradecimientos dados: 1
Agradecimientos: 2 en 2 posts
Registro en: Dec 2013
Mensaje: #12
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
No es que lo dijiste alrevez, no se puede sacar una gramatica de tipo 2 a partir de una gramatica de tipo 3, porque la 3 esta incluida en la 2. Por eso en el ejercicio se podia sacar una gramatica de tipo 3 a partir de una de tipo 2

Un pesimista es un optimista con experiencia
09-12-2013 17:37
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
m68540534 Sin conexión
Profesor del Modulo A
3++ || 4--
*****

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 259
Agradecimientos dados: 246
Agradecimientos: 166 en 68 posts
Registro en: Mar 2013
Mensaje: #13
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
Podría decirse que todas las gramáticas son tipo 1, pero para clasificarlas se toma el grupo menos abarcativo al que pertenece. Tipo 1 no te dan nunca, o son tipo 2 o tipo 3. Si son tipo 2 no se puede obtener el autómata finito, saaaalvo que tenga una gramática equivalente tipo 3, como en este ejercicio, que no fue casualidad, el año pasado hicieron lo mismo, la trampa es a conciencia y caen muchos porque no suelen hacer esta aclaración.

En definitiva para clasificar la gramática lo único que te fijas es que todas las producciones sean de la forma: No terminal -> terminal, o No terminal -> terminal º No terminal ( º es la concatenación), si encontrás alguna producción que no respete eso automáticamente es tipo 2; en el ejercicio la única producción que correspondería a una gramática tipo 3 es la de Y -> cY/c

Para saber si podés hacer el autómata finito simplemente sacás la expresión regular (o si no te sale el lenguaje y te fijas si lo podés expresar con alguna expresión regular). Si encontrás la ER es de tipo 3 y podés hacer el autómata, caso contrario decís que la gramática es de tipo dos y genera un lenguaje no regular entonces no es posible hacer el autómata (muy difícil que suceda, la idea es evaluar como hacés el autómata xD).

Compilado para aprobar la cursada de Matemática Discreta - http://www.utnianos.com.ar/foro/tema-lib...-parciales
09-12-2013 18:42
Envíale un email Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] m68540534 recibio 1 Gracias por este post
rihardmarius (09-12-2013)
brianmel Sin conexión
Militante
Paren el mundo, me quiero bajar
***

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 50
Agradecimientos dados: 29
Agradecimientos: 28 en 5 posts
Registro en: Mar 2013
Mensaje: #14
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
Me quedo (ab)*ac*cba
osea
cuando "despejo" Y, hago Y = c*c, luego concatenandolo con lo anterior queda
(ab)*ac*cZ

y el lenguaje me quedo asi:

L(G1) = { a^n, b^m , c^m , , }
(Este mensaje fue modificado por última vez en: 29-01-2014 17:26 por brianmel.)
29-01-2014 17:13
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
m68540534 Sin conexión
Profesor del Modulo A
3++ || 4--
*****

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 259
Agradecimientos dados: 246
Agradecimientos: 166 en 68 posts
Registro en: Mar 2013
Mensaje: #15
RE: [AYUDA] Ejercicio de Gramatica y Automatas Finitos
La expresión regular no te la pide, igual está bien lo que hiciste, si te fijas más arriba ya estaba resuelta, lo único que sería cc* y no c*c, o sea (ab)*acc*ba, la primera c representaría que al menos debe aparecer una vez, y la otra con el * que se puede repetir indefinidas veces.

Ahora el lenguaje está mal, tiene que ser igual que la expresión regular pero con variables en vez de los *, sería L(G1) = { (a b)^m a c^n b a/ m>=0 ^ n>0}, m puede ser igual que 0 porque no necesariamente tiene que comenzar en ab, podría comenzar con una a, en cambio en el caso de la c en vez de escribirla dos veces como en la expresión regular (cc*) se la escribe una sola vez pero se la eleva a una potencia mayor que 0, por lo tanto el primer valor de n sería 1, por lo que sí o sí deberá aparecer una vez.

Compilado para aprobar la cursada de Matemática Discreta - http://www.utnianos.com.ar/foro/tema-lib...-parciales
30-01-2014 00:23
Envíale un email 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.