Alan Reyes-Figueroa Teoría de la Computación 2023 04.10.2023 Ejemplo de binarización de reglas. (Convertir lado derecho a 2 variables a o 1 terminal) Ejemplo: Binarizar la siguiente gramática (1) Cuando el lado derecho es una cadena de variables A -> XYZW XYZ W = BW B = XYZ A -> BW B -> XYZ XY Z = CZ C = XY C -> XY queda: A -> BW B -> CZ C -> XY ---------------------------------------------- (2) Cuando el lado derecho contiene terminales Sustituimos cada terminal por una variable no usada A -> xYzW Convertimos x a , Convertimos z a , y añadimos las producciones -> x -> z Así: A -> XYZW -> x -> z Ahora usamos el paso (1) para secuenciar la binarización. A -> BW B -> C C -> Y -> x -> z