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:

q₀₁=(q₀₁,q₀₂),

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

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

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,

$$L(\mbox{\it AF\/})=L(\mbox{\it AF\/}_1)\cup L(\mbox{\it AF\/}_2).$$

Ahora, si definimos como conjunto de estados finales al conjunto

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

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,

$$L(\mbox{\it AF\/})=L(\mbox{\it AF\/}_1)\cap L(\mbox{\it AF\/}_2).$$

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