Problema 4.1 (de la Palabra)
Dada una gramática
G y una palabra
![$\sigma$](img17.gif)
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
![$\sigma\in L(G)$](img486.gif)
encontrar una derivación en
G de
![$\sigma$](img17.gif)
a partir del símbolo inicial de
G.
Proposición 4.1
Para toda gramática
![$G_1=\left(V_1,T_1, P_1,s_{01}\right)$](img511.gif)
y exite una gramática equivalente
![$G_2=\left(V_2,T_2, P_2,s_{02}\right)$](img512.gif)
,
con el mismo conjunto de símbolos terminales
T2=
T1, tal que en la nueva gramática las producciones son de la forma
![$\alpha\rightarrow\beta$](img400.gif)
,
donde
![$\alpha\in V_2^*$](img513.gif)
,
y bien
![$\beta\in V_2^*$](img514.gif)
o bien
![$\beta\in T_2$](img515.gif)
,
es decir, consta de un único símbolo terminal. Además, la gramática
G2 es del mismo tipo que la gramática
G1.