Problema 4.1 (de la Palabra)
Dada una gramática
G y una palabra
sobre su alfabeto de símbolos terminales, decidir si acaso la palabra pertenece o no al lenguaje generado por
G.
Problema 4.2 (de Derivación)
Dada una gramática
G y una
encontrar una derivación en
G de
a partir del símbolo inicial de
G.
Proposición 4.1
Para toda gramática
y exite una gramática equivalente
,
con el mismo conjunto de símbolos terminales
T2=
T1, tal que en la nueva gramática las producciones son de la forma
,
donde
,
y bien
o bien
,
es decir, consta de un único símbolo terminal. Además, la gramática
G2 es del mismo tipo que la gramática
G1.