[Ejercicio 4] Simplificación

Re: [Ejercicio 4] Simplificación

de Santiago Gongora -
Número de respuestas: 0
Hola Nicolás,

Respuesta corta: se sacan todas las producciones que del lado derecho tengan una variable que no aparece en el lado izquierdo de ninguna producción ("una variable que no produce nada").

Respuesta larga:
si hay una variable que no aparece nunca del lado izquierdo de una producción, quiere decir que esa variable "no produce nada". De alguna manera se podría decir que esa variable lo único que produce es el conjunto vacío (atención, me refiero a  \emptyset  y no a  \{ \epsilon \} ).

Si lo único que produce "A" es el conjunto vacío, entonces la producción  S \longrightarrow Ab  equivale a  S \longrightarrow \emptyset b y como el conjunto vacío es absorbente (análogo a la multiplicación por 0), entonces  S \longrightarrow \emptyset .  Es decir, S pasaría a generar al conjunto vacío (o sea, nada) y, por lo tanto, es lo mismo que la producción  S \longrightarrow Ab    ya no estuviera.

---------------------- 👁️ OJO 👁️ -------------------------
Por favor, al hacer este tipo de razonamientos tené en cuenta que cuando nos referimos a "una producción" nos estamos refiriendo a una única producción, con las restricciones descritas en la definición de GLC. Por ejemplo, si estás evaluando las producciones de Z y tenés  Z \longrightarrow ccBc | ccX | abbaZ , en realidad ahí tenés 3 producciones, que tenés que analizar por separado:
  1.  Z \longrightarrow ccBc
  2.  Z \longrightarrow  ccX
  3.  Z \longrightarrow abbaZ
---------------------- 👁️👄👁️ -------------------------

A las órdenes,
Santi