Seguimos buscando a Arshak. Ayudanos compartiendo!
Encuesta no oficial de docentes
Resultados de la encuesta no oficial de docentes
Probaste el SIGA Helper?

Donar $100 Donar $200 Donar $500 Donar mensualmente


Enviar respuesta 
 
Calificación:
  • 1 votos - 5 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[M. discreta] lenguajes - ayuda
Autor Mensaje
Intips Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 48
Agradecimientos dados: 12
Agradecimientos: 0 en 0 posts
Registro en: Feb 2009
Mensaje: #1
[M. discreta] lenguajes - ayuda Dudas y recomendaciones Matemática Discreta
Hola, me puse a hacer algunos finales y me tope con esto:

a) indique de que tipo de lenguaje se trata (si es tipo 0,1,2,3)
b)si corresponde diseñar un automata finito que reconozca el lenguaje, de lo contrario diseñar una gramatica que lo genere

y esto es la solucion:
[img][Imagen: disv.png] Uploaded with ImageShack.us[/img]

mis preguntas:

en el punto "a" no entiendo como deduce que es de tipo 2, por el libro puedo reconocer que tipo es mirando sus producciones y si me dan algo asi estoy perdido

en el punto "b" es correcto esto?
" se llama lenguaje tipo 3 o regular y un automata finito se construye sobre expreciones regulares o lenguajes regulares y al ser del tipo 2 no es posible construir el automata finito".

Otra pregunta: si tengo una exprecion regular puedo afirmar que es del lenguaje tipo 3?
31-07-2010 17:24
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.745
Agradecimientos dados: 154
Agradecimientos: 125 en 79 posts
Registro en: Sep 2009
Mensaje: #2
RE: [M. discreta] lenguajes - ayuda
no entiendo, este autómata no generaría el lenguaje?

[Imagen: 80988503.png]



edit: me acabo de dar cuenta del error: es imposible hacer que la cantidad de a^n y c^n sean la misma con un autómata, osea es imposible de establecer el valor de n
(Este mensaje fue modificado por última vez en: 31-07-2010 17:40 por Vallo.)
31-07-2010 17:38
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Intips Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 48
Agradecimientos dados: 12
Agradecimientos: 0 en 0 posts
Registro en: Feb 2009
Mensaje: #3
RE: [M. discreta] lenguajes - ayuda
no entiendo, tu automata me parece que si genera igual cantidad de As y Cs de hecho aa*bc*caaaa* no es una exprecion que genera misma cantidad de As y Cs??
31-07-2010 17:51
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
pablo Sin conexión
ModdIng
Hombre de ingenio (?)
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.637
Agradecimientos dados: 0
Agradecimientos: 24 en 14 posts
Registro en: Apr 2008
Mensaje: #4
RE: [M. discreta] lenguajes - ayuda
Sí, como dice Vallo, no se puede en un lenguaje regular (tipo 3 creo).

Creo que para esto tenés que usar un autómata de pila o algún otro autómata, pero el lenguaje regular no te lo permite, así que es de otro tipo seguro =P.

"No estoy de acuerdo con lo que decís, pero defenderé hasta la muerte vuestro derecho a decirlo" - Voltaire.
31-07-2010 17:52
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
brunodiaz Sin conexión
The Dark Knight
Bla
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 7.707
Agradecimientos dados: 92
Agradecimientos: 384 en 135 posts
Registro en: May 2008
Mensaje: #5
RE: [M. discreta] lenguajes - ayuda
(31-07-2010 17:51)Intips escribió:  no entiendo, tu automata me parece que si genera igual cantidad de As y Cs de hecho aa*bc*caaaa* no es una exprecion que genera misma cantidad de As y Cs??

No
Fijate
aabccccccccccccccaaaa es una expresion valida del automata. Tene en cuenta que el asterisco no representa la misma cantidad para cada vez que aparece. Solo quiere decir 0 mas veces.
31-07-2010 18:29
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.356
Agradecimientos dados: 900
Agradecimientos: 887 en 356 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #6
RE: [M. discreta] lenguajes - ayuda
Ahii te respondooo, bancame que escriboo

[Imagen: v34BEFt.gif]
31-07-2010 18:34
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
guidok Sin conexión
Secretario de la SAE
Sin estado :)
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 450
Agradecimientos dados: 22
Agradecimientos: 109 en 26 posts
Registro en: Dec 2008
Mensaje: #7
RE: [M. discreta] lenguajes - ayuda
Si a vos te dan una definición de un lenguaje, y ves que los exponentes de las letras tienen alguna relación, por ejemplo:

\[L={a^n b^n / n>0\]
\[L={a^n b^t c^2n / n>=0\], que son lenguajes independientes de contexto.

\[L={a^n b^n c^n / n>0\], que es un lenguaje sensible al contexto.

el lenguaje no puede ser nunca de tipo 3, es decir, un lenguaje regular.

Es por eso que:
- No existe una expresión regular con la cual se lo pueda representar.
- No existe un autómata finito que lo reconozca (sí un autómata con pila o una máquina de Turing, pero eso no se ve).

Es decir que la única manera que tenés de representarlo, digamos, es con una gramática.

En el caso del ejercicio que posteaste, es un lenguaje independiente de contexto, con lo cual lo podés representar con una gramática independiente de contexto. Hay infinitas gramáticas equivalentes que pueden representarlo, ahí te ponen una.
31-07-2010 18:39
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.356
Agradecimientos dados: 900
Agradecimientos: 887 en 356 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #8
RE: [M. discreta] lenguajes - ayuda
ah cagense todos, ya me gano de mano =(

[Imagen: v34BEFt.gif]
31-07-2010 18:48
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Intips Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 48
Agradecimientos dados: 12
Agradecimientos: 0 en 0 posts
Registro en: Feb 2009
Mensaje: #9
RE: [M. discreta] lenguajes - ayuda
(31-07-2010 18:39)guidok escribió:  Si a vos te dan una definición de un lenguaje, y ves que los exponentes de las letras tienen alguna relación, por ejemplo:

\[L={a^n b^n / n>0\]
\[L={a^n b^t c^2n / n>=0\], que son lenguajes independientes de contexto.

\[L={a^n b^n c^n / n>0\], que es un lenguaje sensible al contexto.

Primero. muchas gracias a todos por molestarce
y segundo, en los ejemplos que me pasaste veo que todos tienen exponentes con alguna relacion, todos, y no entiendo como reconocer los "lenguajes independientes de contexto" de un "lenguaje sensible al contexto."

por ejm:
\[L={a^n b^n c^n / n>0\]
\[L={a^n b^n c^n / n>0\]
no se a que lenguajes pertenecen pero pareciera que pertenecen al mismo, sin embargo lo definiste como lenguajes distintos.

gracias
31-07-2010 19:01
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.356
Agradecimientos dados: 900
Agradecimientos: 887 en 356 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #10
RE: [M. discreta] lenguajes - ayuda
A VER SI ME DEJAN A MIII =) jaja estoy respondiendo ..!
Creo que la pregunta que haces seria mas facil de explicar si supieses lo que es un automata de pila. Como eso no se ve en discreta, nos la arreglamos con lo que sabes..

Un lenguaje Independiente de contexto es generado por gramaticas Independientes de contexto.
Estas tienen la forma A-->(T+x)* es decir, de un NOTERMINAL-->cualquier combinacion de terminales/no terminales

Un lenguaje Sensible de contexto es generado por gramaticas Sensibles al contexto.
Forma A-->T donde A y T son cualquier combinacion de terminales/no terminales. 2 restricciones nomas: A no puede ser "e" (osea el neutro) y ademas el cardinal de A |A| debe ser menor o igual al de B |B|; es decir, cuando apliques las producciones a la derecha debe haber igual o mayor cantidad de "caracteres" que a la izquierda.

Cual es el dilema con esos lenguajes potenciales ? casi nunca son LR, y como no ves automata de Pila lo mas comodo que podes hacer es generarte una gramatica, y mirando la gramatica decidir que tipo de gramatica es ; con eso sabes que lenguaje genera y por consiguiente su tipo.
Justamente cuando crees una gramatica te dara de la forma de una GIC, es decir que esa GIC genera un LIC, y por lo tanto es Tipo 3.
Consejo: Cuando tengas 2 potencias y hay relacion entre estas(osea los exponentes tienen la misma variable "n"), suelen ser LIC o L. sensibles al contexto (LSC).
Si son solo 2 potencias \[ a^n b^n \] y estan "pegadas" son LIC; ahora si tenes 3 o mas potencias, o no estan "pegadas", (por Ejemplo \[a^n b^t c^n\])seran LSC porquee no tenes manera, con una LIC, de generar ese \[b^t\] en el medio.
En cambio, fijate que si fuese por ejemplo \[a^n b^n c^t\] esta la podes generar con una GIC (para los que estuvimos en sintaxis, lo vimos en Automatas de pila, que lo genera). ¿Por que ? Porque es como generar \[a^n b^n\] y a este concatenarle \[c^t\]. Lo mismo para \[c^t a^n b^n\]; NO ASI para \[a^n b^n c^t d^n e^n \]
Por que esta ultima no ? Tras hacer el \[a^n b^n \] haces el \[ c^t\] y luego cuando quieras hacer el \[d^n e^n\] no tenes forma de saber cuantas "n-veces" hiciste la primera parte. Con "hacer" me refiero cuantas veces aplicaste esa produccion (que en sintaxis veras que se llama derivar)
Por eso fijate, si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC
(ojo que hablamos de exponentes variables, osea, \[a^n\]; y no de por ejemplo \[a^3\]

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 31-07-2010 19:25 por gonnza.)
31-07-2010 19:08
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
guidok Sin conexión
Secretario de la SAE
Sin estado :)
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 450
Agradecimientos dados: 22
Agradecimientos: 109 en 26 posts
Registro en: Dec 2008
Mensaje: #11
RE: [M. discreta] lenguajes - ayuda
(31-07-2010 19:08)gonnza escribió:  Si son solo 2 potencias \[ a^n b^n \] y estan "pegadas" son LIC; ahora si tenes 3 o mas potencias, o no estan "pegadas", (por Ejemplo \[a^n b^t c^n\])seran LSC porquee no tenes manera, con una LIC, de generar ese \[b^t\] en el medio.



Che Gonza pero \[a^n b^t c^n\] es independiente de contexto, no sensible, creo.

Por ejemplo, lo podés generar con esta gramática, que es una GIC:

\[S -> aSc | TT -> bT | b\]
(en este caso con \[n>=0; t>=1\])

La mejor forma de definirlo para mí sería...

- Si hay dos letras que tienen exponentes relacionados, es Independiente. Por ejemplo: \[L={a^n b^t c^n / n>=0;t>=1}\].

- Si hay tres letras que tienen exponentes relacionados, es Sensible. Por ejemplo: \[L={a^n b^n c^m d e^n / n>=1;m>=1}\]
(Este mensaje fue modificado por última vez en: 31-07-2010 19:54 por guidok.)
31-07-2010 19:48
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.356
Agradecimientos dados: 900
Agradecimientos: 887 en 356 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #12
RE: [M. discreta] lenguajes - ayuda
entonces es como yo explique, y eso que dije "excepcion" es en realidad un ejemplo mas =D jkaja
entre todo se me chispoteo xD
la definicion correcta seria algo asi como el mismo exponente aparece HASTA 2 veces, es LIC.

Por ejemplo \[a^n b^n c^t d^t e^x f^x\] es LIC, y aparecen 3 exponentes distintos.. La cosa va en la cantidad de repeticiones de un exponente: Si son mas de 2, tiene que ser LSC, y si son 2 o menos, es LIC

Creo que ahi entre mi amigo guidok y yo te explicamos la duda.. Cualquier cosa, repregunta =)

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 31-07-2010 19:59 por gonnza.)
31-07-2010 19:56
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Intips Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 48
Agradecimientos dados: 12
Agradecimientos: 0 en 0 posts
Registro en: Feb 2009
Mensaje: #13
RE: [M. discreta] lenguajes - ayuda
Perfecto. muchas gracias gonzza, entendi todo lo que escribiste. solo que habria que aclarar esto:

"Justamente cuando crees una gramatica te dara de la forma de una GIC, es decir que esa GIC genera un LIC, y por lo tanto es Tipo 3".

por que en el libro a un LIC se lo conoce como TIPO 2, que es la respuesta al ejercicio que plantie.

no habia leido los ultimos comentarios.

"si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC" me parece que esto esta mal, veredad? por que en el mismo ejercicio que adjunte hay 2 potencias relacionadas y estan separadas y si es LIC. por lo que en sintecis seria:

"no importa si estan pegadas o no, si hay 2 o menos exponentes relacionadas seran LIC y si hay 3 o mas seran LSC"

es asi?
(Este mensaje fue modificado por última vez en: 31-07-2010 20:28 por Intips.)
31-07-2010 20:09
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.356
Agradecimientos dados: 900
Agradecimientos: 887 en 356 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #14
RE: [M. discreta] lenguajes - ayuda
Cita:Perfecto. muchas gracias gonzza, entendi todo lo que escribiste. solo que habria que aclarar esto:

"Justamente cuando crees una gramatica te dara de la forma de una GIC, es decir que esa GIC genera un LIC, y por lo tanto es Tipo 3".

por que en el libro a un LIC se lo conoce como TIPO 2, que es la respuesta al ejercicio que plantie.
My mistake ;) Fe de erratas :
LR---> TIPO 3
LIC---> TIPO 2
LSC-->TIPO 1
LIrrestricto --> TIPO 0;

Cita:si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC" me parece que esto esta mal, veredad? por que en el mismo ejercicio que adjunte hay 2 potencias relacionadas y estan separadas y si es LIC. por lo que en sintecis seria:

"no importa si estan pegadas o no, si hay 2 o menos exponentes relacionadas seran LIC y si hay 3 o mas seran LSC"

es asi?
Estan separadas por "b"; pero cuando nos referimos con guidok a "separadas" nos referimos a separadas por una cantidad indeterminada de caracteres (osea, que no podes saber cuantos hay en el medio". Es decir, cuanto tenes un \[b^x\] en el medio (osea, otro exponente). Eso quise decir cuando puse
Cita:Por eso fijate, si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC
(ojo que hablamos de exponentes variables, osea, \[a^n\] ; y no de por ejemplo \[a^3\]

En el caso de tu ejemplo, vos tenes un "b" en el medio, es decir, siempre hay 1 y solo 1 caracter, no tenes que habra "n-caracteres" (osea, no tenes un rango de cantidad de caracteres posible). Por eso la definicion que te dimos seria correcta cuando "pegados" en el sentido de que no estan separados por algun \[a^x\], osea, por algun exponente distinto.
Quizas no se entendio bien, espero que ahora si =)

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 31-07-2010 20:51 por gonnza.)
31-07-2010 20:51
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Intips Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 48
Agradecimientos dados: 12
Agradecimientos: 0 en 0 posts
Registro en: Feb 2009
Mensaje: #15
RE: [M. discreta] lenguajes - ayuda
Mil gracias che, ahora termino de cerrarme todo. Espero sacarme discreta de ensima, gracias por la ayuda
31-07-2010 21:23
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)