next up previous contents
Siguiente: Propiedades de cerradura Un nivel arriba: Autómatas finitos y expresiones Anterior: Autómatas bidireccionales

Producto de autómatas

Sean $\mbox{\it AF\/}_1=(Q_1,\mbox{\it Ent\/},\mbox{\it tran\/}_1,q_{01},F_1)$ y $\mbox{\it AF\/}_2=(Q_2,\mbox{\it Ent\/},\mbox{\it tran\/}_2,q_{02},F_2)$ dos autómatas finitos. Su semiautómata producto se define sobre el producto cartesiano como sigue:

estados:
$Q=Q_1\times Q_2={[(q_1,q_2)\vert q_1\in Q_1,q_2\in Q_2]}$,
estado inicial:
q01=(q01,q02),
transiciones:
$\begin{array}[t]{rcl}
\mbox{\it tran\/}:Q\times \mbox{\it Ent\/} &\rightarrow& ...
...=\left(\mbox{\it tran\/}_1(q_1,e),\mbox{\it tran\/}_2(q_2,e)\right)
\end{array}$
(se tiene un semiautómata porque aún no hay estados finales). Denotemos por $\mbox{\it AF\/}=\mbox{\it Prod\/}(\mbox{\it AF\/}_1,\mbox{\it AF\/}_2)$ a este semiautómata.

Es evidente que

\begin{eqnarray*}\sigma\in\mbox{\it Ent\/}^*,(q_1,q_2)\in Q &\Rightarrow& \mbox{...
...^* &\Rightarrow& T(\sigma)=\left(T_1(\sigma),T_2(\sigma)\right)
\end{eqnarray*}


Así pues, si definimos como conjunto de estados finales al conjunto

\begin{displaymath}F_{\lor}={[(q_1,q_2)\in Q\vert(q_1\in F_1)\lor(q_2\in F_2)]}\end{displaymath}

entonces una palabra $\sigma \in \mbox{\it Ent\/}^*$ será reconocida por el producto si y sólo si lo es por alguno de los autómatas $\mbox{\it AF\/}_1$ o $\mbox{\it AF\/}_2$, es decir, en este caso,

\begin{displaymath}L(\mbox{\it AF\/})=L(\mbox{\it AF\/}_1)\cup L(\mbox{\it AF\/}_2).\end{displaymath}

Ahora, si definimos como conjunto de estados finales al conjunto

\begin{displaymath}F_{\land}={[(q_1,q_2)\in Q\vert(q_1\in F_1)\land(q_2\in F_2)]}\end{displaymath}

entonces una palabra $\sigma \in \mbox{\it Ent\/}^*$ será reconocida por el producto si y sólo si lo es por ambos autómatas $\mbox{\it AF\/}_1$ o $\mbox{\it AF\/}_2$, es decir, en este caso,

\begin{displaymath}L(\mbox{\it AF\/})=L(\mbox{\it AF\/}_1)\cap L(\mbox{\it AF\/}_2).\end{displaymath}

Naturalmente, un autómata producto puede reducirse de manera equivalente considerando unicamente su parte accesible, es decir, aplicándole el algoritmo 3.5.



Guillermo Morales-Luna
2000-06-27