Eliminación de producciones unitarias[editar]
Dada una gramática independiente del contexto
es una tupla
, donde:
: Conjunto de símbolos no terminales
.
: Conjunto de símbolos terminales (o alfabeto de la gramática).
![{\displaystyle \Sigma \cap V=\emptyset }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6960c0f9ece3eec4f2daa6805dd9b635d02e14c1)
: Símbolo de arranque (Start) o axioma de la gramática
.
: Conjunto de reglas de producción.
![{\displaystyle P=\{A\rightarrow \alpha |A\in V,\alpha \in (V\cup \Sigma )*\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/194d56ff5325243a93bc34bbe501e548e10a6099)
.
Una producción se dice que es unitaria si tiene la forma
. 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:
H = {(A, B)
V
V
A
B}
H =
;
forall (Producción de la forma
) do
H = H
{(A, B)};
end
while (H cambie) do
forall (par de parejas de la forma (A, B)(B, C)) do)
if ((A, C)
H) then
H = H
{(A, C)};
end
end
end
*Eliminar todas las producciones unitarias;
forall (Producción B
) do
forall (pareja (A, B)
H) do
Añadir a la gramática una producción A
end
end
Veamos un ejemplo de aplicación del algoritmo. Consideremos para ello la gramática:
![{\displaystyle S\rightarrow A\vert Aa}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b29392f5c7235a47da15ea3eed019834d12b852)
![{\displaystyle A\rightarrow B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23efef033def56a67de7ded823f14626de26d174)
![{\displaystyle B\rightarrow C\vert b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6ea3240802d0cf258d62e7b19204f8c4419b69c)
![{\displaystyle C\rightarrow D\vert ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff1661e9c2e4ef63c0b4be7b481f8f0132843e16)
![{\displaystyle D\rightarrow b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/231ca7bc196e96505fc28b163721315150685e19)
El primer bucle del algoritmo calcula el conjunto inicial
= {(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:
![{\displaystyle S\rightarrow Aa}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e6e8449aca16e550f6b770d904a5be4ecde257b)
![{\displaystyle B\rightarrow b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8198c29a0217ade84f2fc29ec669f300ce3996db)
![{\displaystyle C\rightarrow ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd38fc3e78b1e8a571970c3ee0d5586fa72528b9)
![{\displaystyle D\rightarrow b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/231ca7bc196e96505fc28b163721315150685e19)
Añadiendo las producciones:
![{\displaystyle A\rightarrow b\vert ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6fe3924a6971d2ab1f7113d5f21f8c032453366)
![{\displaystyle B\rightarrow ab\vert b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/213b59cd487c0077b359a4aea40f95565d03b103)
![{\displaystyle S\rightarrow b\vert ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4670145b32e983bf41a20479022839e3b7289c3)
![{\displaystyle S\rightarrow b\vert ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4670145b32e983bf41a20479022839e3b7289c3)
La gramática finalmente resulta:
![{\displaystyle S\rightarrow Aa\vert ab\vert b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25524d1bd76755857ed879eaa98c216f398d51e5)
![{\displaystyle A\rightarrow ab\vert b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20094658ef449f1d85bd4dd141dc8b6ec06a145e)
![{\displaystyle B\rightarrow ab\vert b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/213b59cd487c0077b359a4aea40f95565d03b103)
![{\displaystyle C\rightarrow ab\vert b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fffe506d10da8b18f8ee0a40d4f6369feb31f4b2)
![{\displaystyle D\rightarrow b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/231ca7bc196e96505fc28b163721315150685e19)
Referencias[editar]