Alan Reyes-Figueroa Teoría de la Computación 2024 23.09.2024 Ejemplo de reducción de una gramática. (Algoritmo de simplificación) Ejemplo: Reducir la siguiente gramática S -> AB | ACA | ab A -> aAa | B | CD B -> bB | bA C -> cC | e D -> aDc | CC | ABb SOLUCIÓN: 1. DEL-e Remover C -> e: S -> AB | ACA | ab | AA A -> aAa | B | CD | D B -> bB | bA C -> cC | c D -> aDc | CC | ABb | C | e Remover D -> e: S -> AB | ACA | ab | AA A -> aAa | B | CD | D | C | e B -> bB | bA C -> cC | c D -> aDc | CC | ABb | C Remover A -> e: S -> AB | ACA | ab | AA | B | AC | CA | A | C | e A -> aAa | B | CD | D | C | aa B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | C | Bb 2. UNIT Producciones unarias: S -> A | B | C A -> B | C | D D -> C Remover D -> C: S -> AB | ACA | ab | AA | B | AC | CA | A | C | e A -> aAa | B | CD | D | C | aa B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c Remover A -> B: S -> AB | ACA | ab | AA | B | AC | CA | A | C | e A -> aAa | CD | D | C | aa | bB | bA | b B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c Remover A -> C: S -> AB | ACA | ab | AA | B | AC | CA | A | C | e A -> aAa | CD | D | aa | bB | bA | b | cC | c B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c Remover A -> D: S -> AB | ACA | ab | AA | B | AC | CA | A | C | e A -> aAa | CD | aa | bB | bA | b | cC | c | aDc | CC | ABb B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c Remover S -> B: S -> AB | ACA | ab | AA | AC | CA | A | C | e | bB | bA | b A -> aAa | CD | aa | bB | bA | b | cC | c | aDc | CC | ABb B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c Remover S -> C: S -> AB | ACA | ab | AA | AC | CA | A | e | bB | bA | b | cC | c A -> aAa | CD | aa | bB | bA | b | cC | c | aDc | CC | ABb B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c Remover S -> A: S -> AB | ACA | ab | AA | AC | CA | e | bB | bA | b | cC | c | aDc | CC | ABb A -> aAa | CD | aa | bB | bA | b | cC | c | aDc | CC | ABb B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c 3. USELESS No hay símbolos que conduzcan a no terminales. Símbolos inalcanzables, no hay. Finalmente la gramática queda así: S -> AB | ACA | ab | AA | AC | CA | e | bB | bA | b | cC | c | aDc | CC | ABb A -> aAa | CD | aa | bB | bA | b | cC | c | aDc | CC | ABb B -> bB | bA | b C -> cC | c D -> aDc | CC | ABb | Bb | cC | c