de nada despues contanos como te fue !

Tengo una duda con un ejercicio similar del libro (pg 395)

32)i)Hallar una gramática G, tipo 3, que genere el lenguaje L(G)= {\[ x^33y^k, k\geq0 \]}

La gramática tipo 3 dice:
x es un único símbolo no terminal
y es concatenación de dos símbolos siendo uno de ellos terminal ó
y es un único símbolo terminal ó y es la palabra nula.

Puedo poner por ejemplo xx? no sé si cuenta como un único símbolo terminal o si serían dos y dejaría de ser tipo tres

La producción que se me había ocurrido para la gramática es:

a---> by/λ
b---> xxx/xxxa

Que ahora me acabo de dar cuenta de que no puede ser tipo 3 porque en una está primero el noterminal y después el terminal , y en la otra está primero el terminal y después el no terminal..., pero la duda es si sigo probando algo parecido o si está mal concatenar simbolos terminales.

A mí también me surgió la duda con ese ejercicio Anirus.

Pero la posta es que cuando hacés x --> y, y no puede estar compuesto por más de 2 símbolos, teniendo que ser uno de ellos -obligatoriamente - terminal.

Y te salió?

Anirus, este lenguaje:

Generalo con esta gramática (aunque parezca fea, es de tipo 3, regular)

S->xN
N->xR
R->xT
T->3|3Z
Z->y|yZ

Corregime si me equivoco, pero creo que es la única forma de hacerlo con una gramática regular.

Respondiendo a tu pregunta, si en alguno ponés, por ejemplo, S->xxxxN, es GIC, pero es una GR ofuscada en una GIC, porque podés hacer exactamente lo mismo con más producciones que sólo tengan un terminal seguido de un noterminal, o un no terminal solo.

Me mandé un error cuando lo pasaba a laTex , era \[x^3^ky^k, k\geq0 \]

Proba con esto, decime si me equivoqué

S-> lambda | xY
Y-> xR
R-> xT
T-> y | yS

(02-08-2010 17:55)Anirus escribió:  Tengo una duda con un ejercicio similar del libro (pg 395)

32)i)Hallar una gramática G, tipo 3, que genere el lenguaje L(G)= {\[ x^33y^k, k\geq0 \]}

La gramática tipo 3 dice:
x es un único símbolo no terminal
y es concatenación de dos símbolos siendo uno de ellos terminal ó
y es un único símbolo terminal ó y es la palabra nula.

Puedo poner por ejemplo xx? no sé si cuenta como un único símbolo terminal o si serían dos y dejaría de ser tipo tres

La producción que se me había ocurrido para la gramática es:

a---> by/λ
b---> xxx/xxxa

Que ahora me acabo de dar cuenta de que no puede ser tipo 3 porque en una está primero el noterminal y después el terminal , y en la otra está primero el terminal y después el no terminal..., pero la duda es si sigo probando algo parecido o si está mal concatenar simbolos terminales.

En ese caso anirus, no no podes hacer xxx como un unico caracter, pues, por la expresion que te dan del lenguaje que generan, te dicen que los simbolos del alfabeto son E={x,y}
Si por ejemplo te dieran \[ (xx)^2 \] y te dicen que el alfabeto es E={xx;y} ahi xx es un unico caracter, por lo que podes (perdon, TENES, porque x no forma parte del alfabeto) que usarlo en las producciones. Nose si entendiste..

(02-08-2010 23:42)Lean escribió:  Proba con esto, decime si me equivoqué

S-> lambda | xY
Y-> xR
R-> xT
T-> y | yS

Funciona sólo para xxxy, para palabras más grandes intecala ys entre las x
xY--->xxR--->xxxT---->xxxyS---->xxxyxY

(02-08-2010 23:46)gonnza escribió:  En ese caso anirus, no no podes hacer xxx como un unico caracter, pues, por la expresion que te dan del lenguaje que generan, te dicen que los simbolos del alfabeto son E={x,y}
Si por ejemplo te dieran \[ (xx)^2 \] y te dicen que el alfabeto es E={xx;y} ahi xx es un unico caracter, por lo que podes (perdon, TENES, porque x no forma parte del alfabeto) que usarlo en las producciones. Nose si entendiste..

Sí, se entiende.

Puta madre.. no se como mierda resolverla.. haciendo una GIC es re facil poniendo S->e | xxxSy... pero pasarla a GR esta jodido

Creo que no hay forma de hacerla.. CREO, la justificación tiene uqe estar en algún lado, si la encuentro edito

---

Por ejemplo la unica forma de hacer esto seria S-> e | xSy... al menos para mi NO HAY otra forma de hacerlo con una GR.

es que esa es un LIC;
no se puede hacer con una GR...

Bueno pero el libro pide hacerla con una GR

Hola, tengo una terrible duda. en la pagina 34, ejercicio 4 de los finales resueltos hay un punto que te pide el diagrama del automata finito y su exprecion regular. hasta aqui coincidimos pero no asi en la ER. estas son las ecuaciones:
a=0a+1b
b=1c + 0a
c= 0c + 1c + lambda (siendo 0,1 los caracteres y a estado inicial, c estado final)

en el parcial operando llega a (0+10)*11(0+1)* , y si se corresponde al automata, pero yo al resolver hago:

a= 0*1b (esto se puede hacer, esta en el libro)
b=1c + 0a
c= (0*1*)* ( he estado haciendo ejercicios y siempre hice esto y siempre me funciono, de hecho en este púnto

coincidimos con el resuelto)

ahora reemplazo a y c en b:

b= 1 (0*1*)* + 00*1b
b= 1 (0*1*)* + (00*1)*

y nada que ver el resultado, y no es equivalente y lo peor de todo sigo todos los pasos como se debe hacer y llego a cualquiercosa. alguien sabe q pasa?? ayuda :-(

(03-08-2010 20:45)Intips escribió:  Hola, tengo una terrible duda. en la pagina 34, ejercicio 4 de los finales resueltos hay un punto que te pide el diagrama del automata finito y su exprecion regular. hasta aqui coincidimos pero no asi en la ER. estas son las ecuaciones:
a=0a+1b
b=1c + 0a
c= 0c + 1c + lambda (siendo 0,1 los caracteres y a estado inicial, c estado final)

en el parcial operando llega a (0+10)*11(0+1)* , y si se corresponde al automata, pero yo al resolver hago:

a= 0*1b (esto se puede hacer, esta en el libro)
b=1c + 0a
c= (0*1*)* ( he estado haciendo ejercicios y siempre hice esto y siempre me funciono, de hecho en este púnto

coincidimos con el resuelto)

ahora reemplazo a y c en b:

b= 1 (0*1*)* + 00*1b
b= 1 (0*1*)* + (00*1)*

y nada que ver el resultado, y no es equivalente y lo peor de todo sigo todos los pasos como se debe hacer y llego a cualquiercosa. alguien sabe q pasa?? ayuda :-(

a=0a1b
b=1c + 0a
c= 0c + 1c + lambda

El c no es (0*1*)* , tenés que agrupar asi (si no me crees volvé a mirar el resuelto ):
c= 0c + 1c + lambda
c= (0+1)c + lamda
c=(0+1)*+lamda = (0+1)*

Ahora reemplazo en b, en esta parte no concatené porque como c es el estado final y no a, no es obligatorio pasar por 0a.

b=1(0+1)* + 0a


Reemplazo en a
a=0a+1 [1(0+1)*+0a]
Distribuyo el 1
a=0a+11(0+1)*+10a
a=0a+10a+11(0+1)*

Factor comun a
a=(0+10)a +11(0+1)*

Concateno(porque la primer parte me deja en a, y como no es estado final si o sí va a tener que pasar por los otros digitos que son los que me llevan a b y luego c)
a=(0+10)*11(0+1)*

Ajam, es logico pero al resolverlo hay que pensarlo asi? digo siguiendo los estados iniciales o finales?? yo he estado resolviendo pensadolos simplemente como ecuaciones y sin importar el diagrama solo despejar. Pasa que he estado practicando pensandolo asi y a un dia del final descubro que no es muy correcta aparentemente.

ademas el libro dice si:

a = 1a entonces a = 1*
si a= 1a + 1b entonces a= 1*1b ( y es esto lo que aplico en c )

todo por seguir el libro, sigo sin entender por q lo q hago esta mal.