UTNianos

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!!

Me respondo a mi mismo:

:blush:

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

PERDON!!!! jajajaaja

GRACIAS IGUAL!!!

Yo diría que es una GIC, (NT) -> (cualquier cosa).

De los capitulos de Muchnik esta en el capitulo 2, jerarquia de Chomsky.
Saludos

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!!

Nota: Una GIC es la que tiene reglas del tipo A->∈ ó A->w A∈NT,w∈T,NT

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.