Equivalencia entre gramáticas lineales por la derecha y autómatas finitos

Sea $M=(\Sigma,Q,\delta,q_0,F)$ un AFD.

Construimos una gramática lineal por la derecha $G$ con $L(G)=L(M)$, es decir, genera el mismo lenguaje que el AFD acepta.

$$G=(\Sigma_N,\Sigma_T,P,\$)=(Q,\Sigma,P,q_0)$$

es decir

• $\Sigma_N=Q$, los estados del autómata determinan los símbolos no-terminales de la gramática
• $\Sigma_T=\Sigma$, los símbolos del autómata determinan los símbolos terminales de la gramática
• $\$=q_0$, el estado inicial del autómata determina el símbolo inicial de la gramática

El sistema de producciones $P$ está dado por:

• Si $\delta(q,\sigma)=p$ es una transición del AFD, con $p,q\in Q$ y $\sigma\in\Sigma$, entonces añadimos a $P$ la producción $q\longrightarrow \sigma p$.
• Si $\delta(q,\sigma)=p$ es una transición del AFD, con $q\in Q$, $p\in F$ y $\sigma\in\Sigma$, entonces añadimos a $P$ la producción $q\longrightarrow \sigma$.
• Si $q_0\in F$, entonces añadimos a $P$ la producción $q_0\longrightarrow \epsilon$.

Ejemplo:

	$a$	$b$	$c$
$\Longrightarrow \star q_0$	$q_0$	$q_1$	$q_2$
$\star q_1$	-	$q_1$	$q_2$
$\star q_2$	-	-	$q_2$

Entonces el sistema de producciones $P$ de la gramática será:

$$\begin{eqnarray*} P&=&\{q_0\longrightarrow aq_0\vert a\vert bq_1\vert b\vert cq... ...ow bq_1\vert b\vert cq_2\vert c,q_2\longrightarrow cq_2\vert c\} \end{eqnarray*}$$

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

Construimos una autómata finito $M$ con $L(M)=L(G)$, es decir, el autómata acepta el mismo lenguaje que la gramática genera.

$$M=(\Sigma,Q,\delta,q_0,F)=(\Sigma_T,\Sigma_N\cup\{f\},\delta,\$,\{f\})$$

es decir,

• $\Sigma_T=\Sigma$, los símbolos terminales de la gramática determinan los símbolos del autómata
• $Q=\Sigma_N\cup\{f\}$, los símbolos no-terminales de la gramática determinan los estados del autómata, y añadimos un nuevo estado $f$, es decir, $f\notin\Sigma_N$
• $q_0=\$, el símbolo inicial de la gramática determina el estado inicial del autómata

Las transiciones $\delta$ están dadas por:

• Si $A\longrightarrow \sigma B$ es una producción de $G$, con $A,B\in\Sigma_N$ y $\sigma\in\Sigma_T$, entonces añadimos la transición $\delta(A,\sigma)=B$.
• Si $A\longrightarrow \sigma$ es una producción de $G$, con $A\in\Sigma_N$ y $\sigma\in\Sigma_T$, entonces añadimos la transición $\delta(A,\sigma)=f$.
• Si $\$\longrightarrow \epsilon$ es una producción de $G$, entonces añadimos la transición $\delta(\$,\epsilon)=f$.

Observamos que el autómata construido es un autómata finito no-determinista (AFND) que podemos convertir en un AFD si hace falta.

Ejemplo:

Para la gramática de arriba--renombrando los símbolos--convertimos

$$\begin{eqnarray*} P&=&\{\$\longrightarrow a\$\vert a\vert bA\vert cB\vert c\ver... ...rightarrow bA\vert b\vert cB\vert c,B\longrightarrow cB\vert c\} \end{eqnarray*}$$

a la tabla de transiciones

	$a$	$b$	$c$
$\Longrightarrow \$	$\{\$,f\}$	$\{A\}$	$\{B,f\}$
$A$	-	$\{A,f\}$	$\{B,f\}$
$B$	-	-	$\{B,f\}$
$\star f$	-	-	-