Gramáticas en Forma Stándard

Una GLC $G=(N,T,P,\Sigma )$ está en forma stándard (o Forma Normal de Greibach) si cada producción tiene la forma:

$\{\begin{array}{l}\Sigma \to \lambda \\ \Sigma \to A\\ A\to a\beta \end{array}\{\begin{array}{l}A\in N\\ \beta \in (N\cup T{)}^{\ast }\\ a\in T\end{array}$

En una GFS cada paso de derivación, a excepción del primero, es $\phi A\psi ⟹\phi a\beta \psi$ y genera al menos un terminal. Así, derivar un string de longitud $n$ requiere como máximo $n+1$ pasos de derivación.

Conversión

Supongamos una GLC bien conformada $G$, cada producción suya tendrá una de las formas:

$\{\begin{array}{ll}\Sigma \to \lambda & A\to a\alpha \\ \Sigma \to A& A\to B\beta \end{array}\{\begin{array}{l}A,B\in N;a\in T\\ a,\beta \in (N\cup T{)}^{\ast };\beta \notin \lambda \end{array}$

Las primeras tres producciones están en forma stándard, y la cuarta (de forma $A\to B\beta$) se convierte por sustitución:

Sea una derivación por izquierda $A⟹X_1{\beta }_1⟹X_2{\beta }_2{\beta }_2⟹\cdots ⟹X_k{\beta }_k\dots {\beta }_2{\beta }_1⟹...$. Esa derivación será finita mientras no se repita un no terminal en la secuencia $A,X_1,\dots ,X_k,\dots$. Si en algún caso se da $X_i=X_j$ se da la derivación $X\stackrel{\ast }{⟹}X{\beta }_j\dots {\beta }_{i+1}$ que es un bucle infinito al derivar por izquierda!!

Eliminación de No Terminales Recursivos por Izquierda

Recursión Directa

Sea la GLC $G$ con las reglas $X$ de $G$:

$$\begin{array}{rl}X& \to {\alpha }_1,\dots X\to {\alpha }_n\\ X& \to X{\beta }_1,\dots X\to X{\beta }_m\end{array}$$

En $G^{\prime }$ se reemplazan esas reglas por:

$$\begin{array}{rl}X& \to {\alpha }_1,\dots X\to {\alpha }_n\\ X& \to {\alpha }_{1}Z,\dots X\to {\alpha }_{n}Z\\ Z& \to {\beta }_1,\dots Z\to {\beta }_m\\ Z& \to {\beta }_{1}Z,\dots Z\to {\beta }_{m}Z\end{array}$$

Se verifica por regla de Arden:

$$\begin{array}{rl}E{R}_G& =X\\ & =({\alpha }_1\cup \cdots \cup {\alpha }_n)\cup X({\beta }_1\cup \cdots \cup {\beta }_m)\\ & =({\alpha }_1\cup \cdots \cup {\alpha }_n)({\beta }_1\cup \cdots \cup {\beta }_m{)}^k\\ E{R}_{G^{\prime }}& =X\\ & =({\alpha }_1\cup \cdots \cup {\alpha }_n)\cup ({\alpha }_1\cup \cdots \cup {\alpha }_n)Z\\ & =({\alpha }_1\cup \cdots \cup {\alpha }_n)\cup ({\alpha }_1\cup \cdots \cup {\alpha }_n)({\beta }_1\cup \cdots \cup {\beta }_m{)}^{\ast }({\beta }_1\cup \cdots \cup {\beta }_m)\\ & =({\alpha }_1\cup \cdots \cup {\alpha }_n)\cup (\lambda \cup ({\beta }_1\cup \cdots \cup {\beta }_m{)}^{\ast }({\beta }_1\cup \cdots \cup {\beta }_m))\\ & =({\alpha }_1\cup \cdots \cup {\alpha }_n)({\beta }_1\cup \cdots \cup {\beta }_m{)}^{\ast }\\ ⟹E{R}_G& =E{R}_{G^{\prime }}\end{array}$$

Recursión Indirecta

Sea $M$ un subconjunto de $N$ en $G$. Sea $G(M)=\{A\to \alpha /A\in M\wedge A\to \alpha \in G\}$ una subgramática de $G$ donde cada regla de $G$ tiene parte izquierda $\in M$. El subconjunto $M$ se elije de manera que no hayan SNRI en $G(M)$. Procedimiento:

1. Sea $X\to Y\beta$ con $Y\in M$ y sean $Y\to {\alpha }_1,\dots ;Y\to {\alpha }_k$. Se reemplaza $X\to Y\beta$ por $X\to {\alpha }_1\beta ,\dots ,{\alpha }_k\beta$. De esta manera se transforman las recursiones indirectas en recursiones directas.
2. Se eliminan los SNRI de recursion directa introducidos en el paso 1.

Dada una GLC cualquiera, es posible construir una GFS fuertemente equivalente.