[2016] [Segundo Parcial] [Ejercicio 4] [Parte a]

[2016] [Segundo Parcial] [Ejercicio 4] [Parte a]

de Enrique Galasso Gonzalez -
Número de respuestas: 3

Estimados, tengo diferencias con la solución que plantean

En la solución se plantean las siguientes reglas de producción:

S --> ITF

T --> ATB | eps

AB --> BAb   (*) (esta regla va agregando una "b" cada vez q cruzo A con B)

......

En el resto de las producciones ni se aumenta ni se disminuye b´s ni a´s. Solo las I y F.

El lenguaje es de la forma a^nb^m siendo "m" la suma de i desde 0 a n.

La regla marcada con (*) lo que hace es duplicar las B´s en función de la cantidad de a'es que hay en la tira.

No veo como llegar a la solución con esas reglas. Lo corrí para el caso n=2 y me genera 4 b´s en vez de 3.

¿Alguna sugerencia?

¿Estoy haciendo algo mal?  


En respuesta a Enrique Galasso Gonzalez

Re: Parcial 2016 Ejercicio 4_a

de Diego Garat -

hola:

la derivación sería la siguiente:

S=>* I AA BB F => I A BA b B F =>*  I ab A B Fb =>*   a I AB F bb => a I ab F bb =>* aa IF bbb => aabbb

¿vos encontraste una que dé cuatro bes? ¿cuál sería?


saludos,

d.-


 

En respuesta a Diego Garat

Re: Parcial 2016 Ejercicio 4_a

de Enrique Galasso Gonzalez -
Gracias por contestar Diego.


En tu derivación cuando pasas de la segunda a la tercera o de la tercera a la cuarta, 

¿qué es lo que te impide de aplicar la regla AB --> BAb?

Si aplicas esa regla es que te encontras con el resultado que planteo ...

¿me explico?

La tira que produzco, ¿no debería de ser independiente del orden o de la cantidad de veces que las aplico? 

Reitero las gracias ...

Enrique

En respuesta a Enrique Galasso Gonzalez

Re: Parcial 2016 Ejercicio 4_a

de Diego Garat -

hola:

si aplico esa regla, nunca llego a tener una tira de terminales:

S=>* I AA BB F => I A BA b B F =>*  I BA b A B Fb => ...=>* IBB AA F bbbb

¿cómo me quito de arriba las variables I, B y A ahora? voy a llegar a una secuencia que contiene variables, a las que no puedo aplicarle ninguna regla... ese resultado no es una tira del lenguaje porque aún contiene símbolos; es una derivación no exitosa.

respecto a tu pregunta: la tira que se produce depende definitivamente del orden en que se aplican las reglas. tenés que garantizar que cualquiera sea ese orden de aplicación el resultado ---que puede ser distinto--- siempre pertenezca al lenguaje dado, donde el resultado es una tira de terminales (las que tienen variables son derivaciones "en proceso" y no son tiras del lenguaje)


saludos,

d.-