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  ->  ACD
	A  ->  a
	B  ->  e
	C  ->  ED | e
	D  ->  BC | e
	E  ->  b


SOLUCIÓN:

1. DEL-e	

	Producciones epsilon:  B -> e, C -> e, D -> e 

	Remover B -> e:

	S  ->  ACD
	A  ->  a
	C  ->  ED | e
	D  ->  BC | C |	e
	E  ->  b

	Remover C -> e:

	S  ->  ACD | AD 
	A  ->  a
	C  ->  ED
	D  ->  BC | C |	B | e
	E  ->  b

	Remover D -> e:

	S  ->  ACD | AD | AC | A 
	A  ->  a
	C  ->  ED | E 
	D  ->  BC | C |	B 
	E  ->  b



2. UNIT

	Producciones unarias:  S -> A, C -> E, D -> C, D -> B

	Remover S -> A:     S -> A -> a

	S  ->  ACD | AD | AC | a 
	A  ->  a
	C  ->  ED | E 
	D  ->  BC | C |	B 
	E  ->  b

	Remover C -> E:     C -> E -> b

	S  ->  ACD | AD | AC | a 
	A  ->  a
	C  ->  ED | b 
	D  ->  BC | C |	B 
	E  ->  b

	Remover D -> C:     D -> C -> ED | b

	S  ->  ACD | AD | AC | a 
	A  ->  a
	C  ->  ED | b 
	D  ->  BC | B | ED | b
	E  ->  b

	Remover D -> B:     D -> B -> no hay 

	S  ->  ACD | AD | AC | a 
	A  ->  a
	C  ->  ED | b 
	D  ->  BC | ED | b
	E  ->  b



3. USELESS / TERM

	Símbolos que no llegan a termino:  B  

	S  ->  ACD | AD | AC | a 
	A  ->  a
	C  ->  ED | b 
	D  ->  ED | b
	E  ->  b


	Símbolos no alcanzables:   No hay. No se remueve nada.


La gramática queda:

	S  ->  ACD | AD | AC | a 
	A  ->  a
	C  ->  ED | b 
	D  ->  ED | b
	E  ->  b






























	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