TeoLeng: [Ejercicio 4] [Parte A] [Parte 4]

Buenas,

Tengo una duda sobre la parte de simplificar esta gramatica. Aplicando el algoritmo, noté lo siguiente:

1 - Eliminar epsilon --> la gramática queda igual ya que no tiene ningún épsilon

2 - Eliminar unitarias --> la gramática queda igual ya que no tiene unitarias.

3 - Positivas --> me quedo el conjunto de { A, C }

4 - Alcanzables --> comenzamos con {S} y agregamos las que alcanza S.

Pero acá viene mi duda, el conjunto de las alcanzables, seria { S, A. C} porque A, C son ambas positivas, pero S no es positiva. Y que pasa con B? porque S es de la forma S -> AB | CA.

¿Me podrían decir donde estoy cometiendo el error?

Otra duda que tengo es, teniendo en cuenta que en la gramática principal tenemos A ->a, yo puedo sustituirlo en los llamados de la variable A, ¿y simplificar la gramática resultante?

S -> aB | Ca

B -> BC | aB

C-> aB |b

Gracias!

(Editado por Santiago Gongora - envío original viernes, 26 de mayo de 2023, 20:49)

Re: [Ejercicio 4] [Parte A] [Parte 3]

de Guillermo Alejo Mena Pastorino - domingo, 28 de mayo de 2023, 13:33

Buenas. Tengo entendido que en este caso S sería positiva por producir CA, que implica dos variables positivas que te permitirían llegar a un elemento de T*. En el ejemplo que se da en las diapositivas subidas, a la hora de obtener las variables positivas se agrega S, que si bien tiene reglas que producen variables no positivas, también contiene reglas que producen variables positivas y eso es suficiente para considerarse variable positiva, según entiendo

Re: [Ejercicio 4] [Parte A] [Parte 3]

de Belen Brandino - lunes, 29 de mayo de 2023, 12:33

hola,
como bien dice Guillermo, S es una variable positiva.

Al principio

$POS_1$ = {A,C} ya que ambas derivan terminales. Luego, a partir de la parte del algoritmo que dice

$si A \notin POS \land A \rightarrow \alpha \in P \land \alpha \in (POS \cup T^*)$ entonces

$POS \leftarrow POS \cup {A}$

como S tiene una producción que genera CA, que son variables que pertenecen a POS (más general pertenecientes a

$POS \cup T^*$ ), entonces S pertenece a POS. No es este el caso de B, ya que ambas producciones de B contienen a B, que no pertenece a POS. Luego, se reescriben las producciones, quitando aquellas que contenían a la variable no positiva B.

En cuanto a tu otra duda, no es parte del algoritmo de simplificación. Podrías hacerlo si queres (justificando), pero no es necesario y tendría que ser aparte del algoritmo

si quedan dudas vuelvan a preguntar

saludos!