[2018] [Segundo Parcial] [Ejercicio 3] [Parte a]

[2018] [Segundo Parcial] [Ejercicio 3] [Parte a]

de Wilson Vera -
Número de respuestas: 2
No me queda claro la producción S -> S1 como se origina desde el planteo de la gramática a la simplificación de las producciones epsilon. Si fuera una producción que faltó en la gramática inicial me parece que estaría de más porque se generaría de la producción S -> A S1 tomando A como epsilon.Ejercicio 3 a)


En respuesta a Wilson Vera

Re: Seg parcial 2018 - ejercicio 3 a)

de Belen Brandino -
Hola,
siguiendo el algoritmo de simplificación,


 tenemos una producción epsilon A  \rightarrow \epsilon  (en la segunda regla). El algoritmo dice que para cada producción que contenga A (Xi ) del lado derecho, tenemos que agregar una regla nueva. En este caso, en la primer regla ( S \rightarrow AS_1 ) tenemos A del lado derecho, por lo cual tenemos que generar la regla nueva que dice el algoritmo. Esta regla es la misma, sacando la A del lado derecho, osea  S \rightarrow S_1  . También hay que hacer esto con la segunda regla, que tiene A del lado derecho también ( A \rightarrow aA  ). Luego, eliminamos la producción epsilon original A \rightarrow \epsilon . Y así queda la regla  S \rightarrow AS_1 | S_2 | S_1

si no queda claro pregunta de nuevo
saludos!