Gramáticas Regulares

En una gramática regular hay una correspondencia entre conjuntos de strings indicados por las letras no terminales de una gramática y ciertos conjuntos de string asociados con los estados de un Aceptor de Estado Finito. Son alternativas a las Expresiones Regulares.

Dada cualquier gramática, se define su lenguaje $L(G,A)$ como el conjunto de strings terminales: $L(G,A)=\{\omega \in T^{\ast }/A\stackrel{\ast }{}⟹\omega \text{ en }G\}$ Sea $M=(Q,S,P,I,F)$ un AEF. Es conjunto final $E(q)$ el conjunto de strings de entrada que llevan a $M$ desde el estado $q$ hasta un estado de aceptación: $E(q)=\{\omega \in S^{\ast }/q\stackrel{\omega }{}⟹q^{\prime }\text{ con }{q}^{\prime }\in F\}$

• Donde $E(q)$ siempre contiene a $\lambda$ siendo $q\in F$.
• Si $q$ no pertenece a $F⟹\lambda \notin E(q)$.
• $\omega$ es admisible $⟺$ existe $q\stackrel{\omega }{⟹}{q}^{\prime }$ en $M$ con $q\in I$ y $q^{\prime }\in F$,

El lenguaje reconocido por $M$ es la unión de todos los $E(q)\forall q\in I$ (estados iniciales).

Proposición 1: sea $M=(Q,S,P,I,F)$ un AEF y $E(q)$ el conjunto final correspondiente a $q$:

1. $\lambda \in E(q)⟺q\in F$,
2. si $\omega =s\phi ⟹\omega \in E(q)⟺\phi \in E(q^{\prime })/q\stackrel{s}{\to }{q}^{\prime }$ en $M$ para algún $q^{\prime }\in Q$.
3. $L(M)=\underset{q\in I}{\cup }E(q)$,

Proposición 2: los conjuntos finaes de un AEF $M=(Q,S,P,I,F)$ satisfacen un sistema de ecuaciones lineales de conjuntos por derecha. $\forall q\in Q:E(q)=\underset{q^{\prime }\in Q}{\cup }V(q,q^{\prime })E(q^{\prime })\cup W(q)$ donde: $V(q,q^{\prime })=\{s\in S/M\text{ tiene }q\stackrel{s}{\to }{q}^{\prime }\}\text{ y }W(q)=\{\begin{array}{l}\lambda \text{ si }q\in F\\ \varphi \text{ de otra manera}\end{array}$

Cada conjunto $V(q,q^{\prime })$ tiene los símbolos de entrada que llevan a $M$ de $q$ a $q^{\prime }$. Se pueden desarrollar ecuaciones lineales de conjuntos en las cuales las incógnitas aparecen como máximo una vez en cada término. Al desarrollar un sistema, notar:

• Si $q$ es estado trampa, entonces $E(q)=\varphi :$ se pueden eliminar términos que incluyan $E(q)$.
• Si $q$ es estado inaccesible, entonces el conjunto de ecuaciones para $E(q)$ puede ser omitido.

Tabla: Construcción de una GRLD a partir de un AEF

Dado un AEF $M=(Q,S,P_M,I,F)$ con conjuntos finales $\{E(q)/q\in Q\}$, se puede construir una gramática lineal $G=(N,S,P_G,\Sigma )$ con $N=\{N(q)/q\in Q\}$ tal que $L(G,N(q))=E(q),q\in Q$.

Regla	Si $M$ tiene	Luego $G$ tiene	Razón
1	$I\cap F\ne \varnothing$	$\Sigma \to \lambda$	$\lambda \in L(M)$
2	$q\in I$	$\Sigma \to N(q)$	$E(q)\subseteq L(M)$
3	$q\stackrel{s}{\to }{q}^{\prime }$, $q^{\prime }\in F$	$N(q)\to s$	$s\in E(q)$
4	$q\stackrel{s}{\to }{q}^{\prime }$	$N(q)\to sN(q^{\prime })$	$E(q)\supseteq sE(q^{\prime })$

Las secuencias de estados en $M$ desde $q\in I$ hasta $q^{\prime }\in F$ tienen una correspondencia uno a uno con las derivaciones de strings terminales a partir de $\Sigma$ en $G$.

Tabla: Construcción de un AEF a partir de una GRLD

Es el proceso inverso. Dada una gramática lineal $G=(N,T,P_G,\Sigma )$, se puede construir un AEF $M=(Q,T,P_M,I,\{q_F\})$ con $Q=\{q_A/A\in N\}\cup \{q_F\}$ y conjuntos finales $\{E(q)/q\in Q\}$ tal que $L(G,a)=E(q_A)$ para $A\in N\cup \{\Sigma \}$.

Regla	Si $G$ tiene	Luego $M$ tiene	Razón
1	$\Sigma \to \lambda$	$q_F\in I$	$\lambda \in L(G)$
2	$\Sigma \to A$	$q_A\in I$	$L(G,A)\subseteq L(G)$
3	$A\to s$	$q_A\stackrel{s}{\to }{q}_F$	$s\in L(G,A)$
4	$A\to sB$	$q_A\stackrel{s}{\to }{q}_B$	$L(G,A)\supseteq sL(G,B)$

Equivalencia entre GRLD y GRLI

Se establece una correspondencia uno a uno entre todas las producciones de $G$ y $G^{\prime }$ de forma que una derivación $\Sigma ⟹s_1{A}_1⟹\cdots ⟹s_1\dots s_k{A}_k⟹s_1\dots s_k{s}_{k+1}$ en $G$ corresponde a $\Sigma ⟹A_k{s}_{s+1}⟹\cdots ⟹A_1{s}_2\dots s_k{s}_{k+1}⟹s_1{s}_2\dots s_k{s}_{k+1}$ en $G^{\prime }$ y por lo tanto $L(G)=L(G^{\prime })$.

Si $G$ tiene	Luego $G^{\prime }$ tiene
$\Sigma \to sA$	$A\to s$
$A\to sB$	$B\to As$
$A\to s$	$\Sigma \to As$
$\Sigma \to s$	$\Sigma \to s$
$\Sigma \to \lambda$	$\Sigma \to \lambda$

Se define el conjunto inicial $B(q)=\{\omega /q^{\prime }\stackrel{\omega }{}⟹q,q^{\prime }\in I\}$ de forma que $L(G,N(q))=B(q)$ para una GRLI con $N=\{N(q)/q\in Q\}$.