Equivalencia entre gramáticas lineales por la derecha y lineales por la izquierda

Como era de esperar, gramáticas lineales por la derecha y gramáticas lineales por la izquierda describen el mismo `fenómeno', es decir, generan los lenguajes regulares.

Sea $G=(\Sigma_N,\Sigma_T,P,\$)$ una gramática lineal por la derecha, es decir, $P\subset\Sigma_N\times(\Sigma_N.\Sigma_T\cup\Sigma_T)\cup\{\$\longrightarrow \epsilon\}$.

Construimos una gramática $G^\prime=(\Sigma^\prime_N,\Sigma_T,P^\prime,\$)$ lineal por la izquierda con el siguiente algoritmo en cuatro pasos:

1. Si el símbolo inicial $\$ de $G$ aparece a la derecha en una producción de $P$, se sustitue $\$ en dichas reglas de la siguiente manera:
   • Se introduce un nuevo símbolo no-terminal $\$^\prime$, es decir, $\Sigma^\prime_N=\Sigma_N\cup\{\$^\prime\}$.
   • Por cada regla de forma $\$\longrightarrow \alpha$ con $\alpha\in\Sigma_N.\Sigma_T\cup\Sigma_T$ se crea una nueva regla $\$^\prime\longrightarrow \alpha$.
   • Cada regla de forma $X\longrightarrow \$\sigma$ ( $X\in\Sigma_N,\sigma\in\Sigma_T$) se sustitue por $X\longrightarrow \$^\prime\sigma$.
   • Si $\$\longrightarrow \epsilon\in P$, se añade para cada regla $X\longrightarrow \$\sigma$ ( $X\in\Sigma_N,\sigma\in\Sigma_T$) la regla $X\longrightarrow \sigma$.
   Con esas modificaciones obtenemos un nuevo sistema de producciones $\overline{P}$ y un alfabeto de variables o bien $\Sigma_N^\prime=\Sigma_N$ o bien $\Sigma_N^\prime=\Sigma_N\cup\{\$^\prime\}$.

2. Se crea un grafo dirigido con las siguientes propiedades:
   • El conjunto de nodos es $\Sigma^\prime_N\cup\{\epsilon\}$.
   • Se añade una arista entre los nodes $A$ y $B$ con atributo $\sigma$, si existe una regla $A\longrightarrow \sigma B$ en $\overline{P}$.
   • Se añade una arista entre los nodes $A$ y $\epsilon$ con atributo $\sigma$, si existe una regla $A\longrightarrow \sigma$ en $\overline{P}$.
   • Se añade una arista entre los nodes $\$ y $\epsilon$ con atributo $\epsilon$, si existe la regla $\$\longrightarrow \epsilon$ en $\overline{P}$.

3. Se `inverte' el grafo, más preciso:
   • Se intercambian los nodos $\$ y $\epsilon$.
   • Se invierte la dirección de todas las aristas.

4. Se transforma el grafo obtenido en el conjunto de reglas $P^\prime$:
   • Para cada arista entre $A$ y $B$ con atributo $\alpha$ se crea una regla $A\longrightarrow B\alpha$ ( $A\in\Sigma_N^\prime, B\in\Sigma_N^\prime\cup\{\epsilon\}$ y $\alpha\in\Sigma_T\cup\{\epsilon\}$).

Ejemplo: Partimos de la gramática

$$G=(\{\$,A\},\{0,1\},\{\$\longrightarrow \epsilon\vert 1A,A\longrightarrow 0\$\vert\},\$)$$

1. el símbolo inicial $\$ aparece a la derecha entonces:
   • Introducimos un nuevo símbolo no-terminal $\$^\prime$.
   • Añadimos la regla $\$^\prime\longrightarrow 1A$.
   • Sustituimos la regla $A\longrightarrow 0\$ por $A\longrightarrow 0\$^\prime$
   • siendo $\$\longrightarrow \epsilon\in P$, añadimos la regla $A\longrightarrow 0$ (pero que ya está en $P$)
   Queda el sistema de producciones intermedio como
   
   $$\overline{P}=\{\$\longrightarrow \epsilon\vert 1A,A\longrightarrow 0\$^\prime\vert,\$^\prime\longrightarrow 1A\}$$
   
   

2. El grafo reflejando dichas reglas es:

   

3. Y el grafo invertido es:

   

4. con lo cual obtenemos el conjunto de reglas:
   
   $$P^\prime=\{\$\longrightarrow \epsilon\vert A0,A\longrightarrow \$^\prime1\vert 1,\$^\prime\longrightarrow A0\}$$