Gramáticas en Forma Normal

Una GLC $G=(N,T,P,\Sigma )$ está en forma normal si cada producción tiene la forma:

$\{\begin{array}{ll}\Sigma \to \lambda & A\to BC\\ \Sigma \to A& A\to a\end{array}\{\begin{array}{l}A,B,C\in N\\ a\in T\end{array}$

Cada paso extiende en uno la longitud o genera un símbolo terminal, asegurando que para un string de longitud $n$ se requieren exactamente $2n$ pasos de derivación. Dada una GLC cualquiera, se puede construir con expansiones una GFN fuertemente equivalente.

Sea $CC(A,\omega )$ la función recursiva que verifica si $A⟹\omega$. Existe un algoritmo de Análisis Sintáctico $CC(A,\omega )$ que funciona de la siguiente manera:

1. Si $|\omega |>1$, dividirlo en $\phi$ y $\psi$, $\omega =\phi \psi$. Para cada regla de la forma $A\to UV$, intentar $CC(U,\phi )$ y $CC(V,\psi )$.
2. Si $|\omega |=1$, buscar una regla $A\to \omega$.

Análisis Sintáctico CYK

La forma normal permite aplicar el algoritmo de análisis sintáctico CYK (Cocke-Younger-Kasami), el cual dado un string $\omega$ y una GLC $G$ en forma normal permite decidir si $\omega \in L(G)$. Procedimiento:

$$\begin{array}{rlr}& \text{Para }i=1\dots n\text{ hacer}& \\ & t_{i1}=\{A/A\to a_i\}& \\ & \text{Para }j=2\dots n\text{ hacer}& \\ & \text{Para }i=1\dots (n-j+1)\text{ hacer}& \\ & t_{ij}=\varphi & \\ & \text{Para }k=1\dots (j-1)\text{ hacer}& \\ & t_{ij}=t_{ij}\cup \{A/A\to BC,\text{ con }B\in t_{ik}\text{ y }C\in t_{i+kj-k}\}& \\ & \text{Si }\Sigma \to S\text{ y }S\in t_{1n}\text{ entonces }\omega \in L(G)& \end{array}$$