Sean G1 y G2 dos gramáticas con un mismo conjunto de símbolos terminales. Diremos que G2subsume a G1 si toda palabra generada en G1 es también generada en G2, es decir, si
.
Escribiremos en este caso
.
Proposición 3.1
La relación de subsunción es una relación reflexiva y transitiva en la clase de gramáticas con un alfabeto terminal fijo.
La subsunción no es antisimétrica pues dos gramáticas distintas pueden generar a un mismo lenguaje.
Una condición suficiente, mas no necesaria, para revisar si acaso una gramática queda subsumida por otra la da la siguiente
Observación 3.1
Sean
y
dos gramáticas con un mismo alfabeto. Si para cada producción
se tiene que
,
entonces
.
Y, en efecto, si
y
es una derivación de
a partir del símbolo inicial s0 en G1, y para cada j,
se deriva de
mediante una derivación
en G2, entonces la concatenación de estas últimas derivaciones ha de dar una derivación de
a partir del símbolo inicial s0 en G2.
Dos gramáticas son equivalentes si cualquiera de ellas subsume a la otra, es decir,
La relación de equivalencia es, efectivamente, una relación de equivalencia en la clase de gramáticas con un alfabeto terminal fijo.
La relación de subsunción es en efecto una relación de orden en el cociente de las gramáticas con un mismo conjunto de símbolos terminales partido por la relación de equivalencia.