Donar $20 Donar $50 Donar $100 Donar mensualmente
 


Enviar respuesta 
 
Calificación:
  • 1 votos - 5 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
SSL duda ejercicio final
Autor Mensaje
repuken2 Sin conexión
Empleado de Fotocopiadora
Internado
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 42
Agradecimientos dados: 60
Agradecimientos: 4 en 2 posts
Registro en: May 2008
Mensaje: #1
SSL duda ejercicio final Finales y 1 más Sintaxis y Semántica de los Lenguajes
Buenas gente,

al final rescate finales de campus, estaban todos, una duda que tengo con los ultimos finales 2010:

en un ejercicio te pide determinar que tipo de gramatica es, te dan las producciones y tenes que decir si es GR, GIC u OTRA.

ejemplo:

S -> aSa | bSb | c

Yo se que no es GR poque del lado izquiero hay aSa y bSb que no son validos para una GR y ponene en la resolucion que es una GIC, Gramatica Independiente del Contexto.

Alguien tiene idea de cual es la definicion de una GIC o como darse cuenta si es GIC ? busque en todos los apuntes y no encontre nada, en el libro de muchnik hay unas definiciones cortitas que no te dicen nada.

Alguien sabe?

Muchas Gracias!!

Suerte para todos mañana!!
28-02-2010 14:23
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
repuken2 Sin conexión
Empleado de Fotocopiadora
Internado
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 42
Agradecimientos dados: 60
Agradecimientos: 4 en 2 posts
Registro en: May 2008
Mensaje: #2
Re: SSL duda ejercicio final
Me respondo a mi mismo:

:blush:

esta en uno de los apuntes donde explica automatas de pila APD.

PERDON!!!! jajajaaja

GRACIAS IGUAL!!!
28-02-2010 14:27
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
esimo Sin conexión
Empleado del buffet
con estado
*

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 18
Agradecimientos dados: 14
Agradecimientos: 3 en 1 posts
Registro en: Dec 2008
Mensaje: #3
Re: SSL duda ejercicio final
Yo diría que es una GIC, (NT) -> (cualquier cosa).

De los capitulos de Muchnik esta en el capitulo 2, jerarquia de Chomsky.
Saludos
28-02-2010 17:41
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
cristian20 Sin conexión
Empleado del buffet
Sin estado :(
*

Ing. en Sistemas
Facultad Regional Mendoza

Mensajes: 7
Agradecimientos dados: 0
Agradecimientos: 0 en 0 posts
Registro en: Dec 2009
Mensaje: #4
Re: SSL duda ejercicio final
Para mí es una gramática independiente del contexto, el lenguaje que se forma es L={wcw^R / w∈{a,b}*} , es imposible llevar una referencia con una GR , por eso para mí es GIC, ya que se puede implementar un autómata a pila que reconozca el lenguaje generado.
Por ejemplo el siguiente autómata:
AP={(a,b,c),(S,a,b),Q,q0,A0,F,f} Q={q}(conj. estados), q0=q(estado inicial),A0=S(símbolo inicial de la pila) F={q}(estado final) ,f=función de transición
f(q,a,S)=(q,Sa)
f(q,b,S)=(q,Sb)
f(q,a,a)=(q,∈)
f(q,b,b)=(q,∈)
f(q,c,S)=(q,∈)

Fijate porque lo hice a las apuradas, creo que te acepta por estado final y por vaciado de pila. La mayoría de las veces yo hago eso, busco el autómata que me reconozca el lenguaje de la gramática.
Saludos!!
Suerte!! thumbup3

Nota: Una GIC es la que tiene reglas del tipo A->∈ ó A->w A∈NT,w∈T,NT
01-03-2010 00:45
Envíale un email Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
alejo89 Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 28
Agradecimientos dados: 0
Agradecimientos: 3 en 3 posts
Registro en: Dec 2008
Mensaje: #5
RE: SSL duda ejercicio final
Es una GIC.

Una GR no puede ser, ya que estas del lado Derecho tienen la forma: aS, Sa, a, epsilon

Una GQR tampoco, ya que estas son GR largas que son simplificadas.
EJ:
S->aT | bT | cT | dT | eT|...|zT
T->a|b
N->a|b|c|...|z

Esta gramatica se puede simplificar de la siguiente manera:
S->NT
T->a|b
N->a|b|c|...|z

Por ende analicemos si es una GIC.

Una GIC del lado Izq tiene solo NoTerminales. Esta cumple eso. Y del lado derecho no hay restricciones. Tambien lo cumple.
18-12-2010 10:04
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.