Usuario:Escaldon/Eliminación de producciones unitarias

Eliminación de producciones unitarias

Dada una gramática independiente del contexto $G$ es una tupla $G\equiv (V,\Sigma ,S,P)$, donde:

$V$: Conjunto de símbolos no terminales $(V\neq \emptyset )$.
$\Sigma$: Conjunto de símbolos terminales (o alfabeto de la gramática).
$\Sigma \cap V=\emptyset$
$S$: Símbolo de arranque (Start) o axioma de la gramática $(S\in V)$.
$P$: Conjunto de reglas de producción.
$P=\{A\rightarrow \alpha |A\in V,\alpha \in (V\cup \Sigma )*\}$
$P\subset Vx(V\cup \Sigma )*,(P\neq \emptyset )$.
Una producción se dice que es unitaria si tiene la forma $A\rightarrow B(A,B\in V)$. Las producciones unitarias hacen a la gramática innecesariamente compleja ya que simplemente renombran un símbolo no terminal. Este algoritmo elimina las producciones unitarias de una gramática G basándose en la construcción del conjunto H definido como:

Algoritmo

H = {(A, B)$\in$ V $\times$ V $\vert$ A $\Rightarrow ^{*}$ B}

H = $\emptyset$;
forall (Producción de la forma $A\rightarrow B$) do
  $\mid$  H = H $\cup$ {(A, B)};
end
while (H cambie) do
  $\mid$  forall (par de parejas de la forma (A, B)(B, C)) do)
  $\mid$     $\mid$  if ((A, C) $\in$ H) then
  $\mid$     $\mid$   $\mid$    H = H $\cup${(A, C)};
  $\mid$     $\mid$  end
  $\mid$   end
end
*Eliminar todas las producciones unitarias;
forall (Producción B $\rightarrow \alpha$) do
  $\mid$   forall (pareja (A, B) $\in$ H) do
  $\mid$     $\mid$  Añadir a la gramática una producción A $\rightarrow \alpha$
  $\mid$   end
end

Ejemplos

Veamos un ejemplo de aplicación del algoritmo. Consideremos para ello la gramática:

$S\rightarrow A\vert Aa$
$A\rightarrow B$
$B\rightarrow C\vert b$
$C\rightarrow D\vert ab$
$D\rightarrow b$

El primer bucle del algoritmo calcula el conjunto inicial

$H_{0}$ = {(SA), (AB), (BC), (CD)}

El bucle while calcula el conjunto de pares:

H = {(SA), (AB), (BC), (CD), (SB), (AC), (BD), (SC), (SD), (AD)}

Al eliminar las producciones unitarias, la gramática resulta:

$S\rightarrow Aa$
$B\rightarrow b$
$C\rightarrow ab$
$D\rightarrow b$

Añadiendo las producciones:

$A\rightarrow b\vert ab$
$B\rightarrow ab\vert b$
$S\rightarrow b\vert ab$
$S\rightarrow b\vert ab$

La gramática finalmente resulta:

$S\rightarrow Aa\vert ab\vert b$
$A\rightarrow ab\vert b$
$B\rightarrow ab\vert b$
$C\rightarrow ab\vert b$
$D\rightarrow b$

Referencias

• Kelley, Dean (1995). Teoría de Autómatas y Lenguajes Formales. Prentice Hall. ISBN 0-13-518705-2.