Conjuntos Traverse

Sea $M=(Q,S,U,P,I,F)$ un APD propio. Una secuencia de movimientos $(q,\phi ,\sigma )⟹(q^{\prime },{\phi }^{\prime },{\sigma }^{\prime })$ es un traverse de $\omega$ desde el estado $q$ al $q^{\prime }$ si se cumple que:

1. $\sigma ={\sigma }^{\prime }$.
2. $\phi \omega ={\phi }^{\prime }$.
3. $\forall (q_i,\phi ,{\sigma }_i):|{\sigma }_i|\ge |\sigma |$ que ocurre dentro de la secuencia de movimientos.

Si la secuencia es traverse se indica:

$(q,\phi ,\sigma )\stackrel{T}{⟹}(q^{\prime },\phi \omega ,\sigma )$

El conjunto Traverse se define de la siguiente manera:

$T(q,q^{\prime })=\{\omega \in S^{\ast }/(q,\phi ,\sigma )\stackrel{T}{}⟹(q^{\prime },\phi \omega ,\sigma );\phi \in S^{\ast },\sigma \in U^{\ast }\}$

Un traverse trivial observa el string vacío: $(q,\phi ,\sigma )\stackrel{T}{⟹}(q,\phi ,\sigma )$ de forma que $\lambda \in T(q,q)\forall q\in Q$.

Propiedades:

1. Si $(q,\phi ,\sigma )\stackrel{T}{⟹}(q^{\prime },\phi \omega ,\sigma )$ es un traverse de $\omega$ para algún $varphi\in S^{\ast }$ y algún $\sigma \in U^{\ast }$, entonces es traverse de $\omega \forall \phi \in S^{\ast }$ y $\forall \sigma \in U^{\ast }$.
2. Si $\phi =\omega =\lambda ⟹(q,\lambda ,\lambda )\stackrel{T}{⟹}(q^{\prime },\omega ,\lambda )$ es una secuencia de aceptación de $\omega$, si $q\in I$ y $q^{\prime }\in F$.
3. Un APD $M$ acepta $\omega ⟺\omega \in T(q,q^{\prime });q\in I,q^{\prime }\in F$, por lo tanto el lenguaje reconocido por $M$ es $L(M)=\bigcup _{\genfrac{}{}{0ex}{}{q\in I}{q^{\prime }\in F}}T(q,q^{\prime })$.
4. Sea $M$ un $APDP:\lambda \in T(q,q^{\prime })⟺q=q^{\prime }$, por lo que cada traverse no trivial de un APDP debe contener como mínimo un scan.

Sea $(q,\phi ,\sigma )\stackrel{T}{⟹}(q^{\prime },\phi \omega ,\sigma )$ un traverse realizado por un APD, siendo $\sigma$ el contenido inicial y final de la pila. Se analiza:

• Se considera write básico un write que se realiza desde una configuración con pila igual a $\sigma$.
• Se considera read básico un read que deja a la pila conteniendo $\sigma$.
• Un write básico y un read básico forman un par de igualdad o coincidencia. Para que la secuencia sea traverse, todo elemento escrito a la pila debe ser leído (para $\sigma$ constante).
• Por ende, un traverse que contiene un read básico también contiene el write básico correspondiente, y viceversa.

Sea $M$ un APDP y $(q,\phi ,\sigma )\stackrel{T}{⟹}(q^{\prime },\phi \omega ,\sigma )$ un traverse de $\omega$ realizado por $M/\omega \in T(q,q^{\prime })⟹$ exactamente una de las siguientes afirmaciones es cierta:

1. $S:(q,\phi ,\sigma )\stackrel{S}{\to }(q^{\prime },\phi s,\sigma )$ donde $\omega =s$.
2. $TS:(q,\phi ,\sigma )\stackrel{T}{⟹}(q^{\prime \prime },\phi \psi ,\sigma )\stackrel{S}{\to }(q^{\prime },\phi \psi s,\sigma )$ donde $\omega =\psi s\wedge \psi \in T(q,q^{\prime \prime })$.
3. $TWTR:(q,\phi ,\sigma )\stackrel{T}{⟹}(q^{\prime \prime },\phi \psi ,\sigma )\stackrel{W}{\to }(p,\phi \psi ,\sigma u)\stackrel{T}{⟹}(p^{\prime },\phi \psi \theta ,\sigma u)\stackrel{R}{\to }(q^{\prime },\phi \psi \theta ,\sigma )$ donde $\omega =\psi \theta$.
4. $WTR:(q,\phi ,\sigma )\stackrel{W}{\to }(p,\phi ,\sigma u)\stackrel{T}{⟹}(p^{\prime },\phi \theta ,\sigma u)\stackrel{R}{\to }(q^{\prime },\phi \theta ,\sigma )$ donde $\omega =\theta$ y $\theta \in T(p,p^{\prime })$.

Para todo $\omega \in S^{\ast }$ de una GLC $G$, sea $N$ un no terminal, se verifica $N(q,q^{\prime })\stackrel{\ast }{⟹}\omega ⟺\omega \in T(q,q^{\prime })$ y cada tipo de traverse se puede correlacionar a una producción (derivación):

Expresiones iniciales	Resultado final con $N$
$(q,\phi ,\sigma )\stackrel{S}{\to }(q^{\prime },\phi S,\sigma )$	$N(q,q^{\prime })\Rightarrow s$
$(q,\phi ,\sigma )\stackrel{T}{\Rightarrow }(q^{\prime \prime },\phi \psi ,\sigma )\stackrel{S}{\to }(q^{\prime },\phi \psi S,\sigma )$	$N(q,q^{\prime })\Rightarrow N(q,q^{\prime \prime })s$
$(q,\phi ,\sigma )\stackrel{T}{\Rightarrow }(q^{\prime \prime },\phi \psi ,\sigma )\stackrel{W}{\to }(p,\phi \psi ,\sigma u)\stackrel{T}{\Rightarrow }(p^{\prime },\phi \psi \theta ,\sigma u)\stackrel{R}{\to }(q^{\prime },\phi \psi \theta ,\sigma )$	$N(q,q^{\prime })\Rightarrow N(q,q^{\prime \prime })N(p,p^{\prime })$
$(q,\phi ,\sigma )\stackrel{W}{\to }(p,\phi ,\sigma u)\stackrel{T}{\Rightarrow }(p^{\prime },\phi \theta ,\sigma u)\stackrel{R}{\to }(q^{\prime },\phi \theta ,\sigma )$	$N(q,q^{\prime })\Rightarrow N(p,p^{\prime })$

Todo conjunto traverse relevante a la construcción de $G$ es $\{T(q,q^{\prime })/q\in B,q^{\prime }\in Q\}$ por lo que queda $N=\{N(q,q^{\prime })/q\in B,q^{\prime }\in Q\}$ con $B=I\cup \{q^{\prime }/q]\text{ write}(u,q^{\prime })\in P\}$, siendo $q$ un estado inicial o sucesor de un write.

Tabla: Construcción de una GLC a Partir de un APDP

Dado un APDP $M=(Q,S,U,P_M,I,F)$, se puede construir una GLC $G=(N,S,P_G,\Sigma )$ tal que $L(G)=L(M)$. Sean $B=I\cup \{q^{\prime }/q]\text{ write}(u,q^{\prime })\in P_M\}$ y $N=\{N(q,q^{\prime })/q\in B,q^{\prime }\in Q\}$. Las producciones de $G$ son las siguientes:

Regla	Si $M$ tiene	Luego $G$ tiene
1	$q^{\prime }]\text{scan}(s,q^{\prime })q\in B$	$N(q,q^{\prime })\to s$
2	$q^{\prime \prime }]\text{scan}(s,q^{\prime })q\in B$	$N(q,q^{\prime })\to N(q,q^{\prime \prime })s$
3	$q^{\prime \prime }]\text{write}(u,p)$ $p^{\prime }]\text{read}(u,q^{\prime })q\in B$	$N(q,q^{\prime })\to N(q,q^{\prime \prime })N(p,p^{\prime })$
4	$q]\text{write}(u,p)$ $p^{\prime }]\text{read}(u,q^{\prime })q\in B$	$N(q,q^{\prime })\to N(p,p^{\prime })$
5	$q\in I$, $q^{\prime }\in F$	$\Sigma \to N(q,q^{\prime })$
6	$I\cap F\ne \varnothing$	$\Sigma \to \lambda$