Alan Reyes-Figueroa Teoría de la Computación 2023 04.10.2023 Ejemplo de reducción de una gramática. (Algoritmo de simplificación) Ejemplo: Reducir la siguiente gramática S -> ACD A -> a B -> e C -> ED | e D -> BC | e E -> b 1. DEL-e borramos B -> e S -> ACD A -> a C -> ED | e D -> BC | C | e E -> b borramos C -> e S -> ACD | AD A -> a C -> ED D -> BC | B | C | e E -> b borramos D -> e S -> ACD | AC | AD | A A -> a C -> ED | E D -> BC | B | C E -> b 2. UNIT Producciones unarias: S -> A, C -> E, D -> B, D -> C Borramos S -> A -> a S -> ACD | AC | AD | a A -> a C -> ED | E D -> BC | B | C E -> b Borramos C -> E -> b S -> ACD | AC | AD | a A -> a C -> ED | b D -> BC | B | C E -> b Borramos D -> B -> No hay Borramos D -> C -> ED C -> b S -> ACD | AC | AD | a A -> a C -> ED | b D -> BC | ED | b E -> b S A C D a E b B 3. USELESS Todos los símbolos son alcanzables. a b S A C D E (B no lleva a terminales) Remover D -> BC S -> ACD | AC | AD | a A -> a C -> ED | b D -> ED | b E -> b