Siguiente: Lema de bombeo Un nivel arriba: Expresiones regulares Anterior: PB visto como un

Minimización de autómatas

Sea $\mbox{\it Ent\/}$ un alfabeto finito. Según vimos anteriormente la noción de lenguaje regular puede presentarse mediante el reconocimiento por autómatas finitos, sean deterministas o no, o mediante la representación por expresiones regulares. Otras presentaciones equivalentes de esta noción se dan en la siguiente:

Proposición 6.1 (Teorema de Myhill-Nerode)   Sea $L\subset\mbox{\it Ent\/}^*$ un lenguaje arbitrario. Las siguientes aseveraciones son equivalentes a pares:

1.

L es regular.

2.

L es la unión de algunas clases de equivalencia de una relación de equivalencia de índice finito, congruente por la derecha con la concatenación de palabras.

3.

La relación $\equiv_L\subset\left(\mbox{\it Ent\/}^*\right)^2$ tal que

$$\forall \sigma,\tau\in\mbox{\it Ent\/}^*:\ \sigma\equiv_L \ta... ...\cdot\upsilon\in L\Leftrightarrow \tau\cdot\upsilon\in L\right)$$

es una relación de índice finito.

Demostración: $1. \Rightarrow 2.$ Supongamos L regular. Sea $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ un autómata finito tal que $L=L(\mbox{\it AF\/}$. Consideremos la función

$$T:\sigma\mapsto T(\sigma)=\mbox{\it tran\/}^*(q_0,\sigma),$$

y su kernel:

$$\forall \sigma,\tau\in\mbox{\it Ent\/}^*:\ \sigma\equiv_K \tau\Leftrightarrow T(\sigma)=T(\tau).$$

Hemos visto que ``$\equiv_K$'' es una relación de equivalencia de índice finito (de hecho este índice está acotado por la cardinalidad de Q), congruente por la derecha. Se tiene además

$$L=\bigcup_{T(\sigma)\in F} [\sigma]_{\equiv_K}.$$

Así pues, se cumple 2.

$2. \Rightarrow 3.$ Sea $R\subset\left(\mbox{\it Ent\/}^*\right)^2$ una relación de equivalencia de índice finito, congruente por la derecha con la concatenación de palabras, tal que para un subconjunto ${\cal F}\subset Q/R$ se tiene que $L={\displaystyle \bigcup_{[\sigma]\in{\cal F}}[\sigma]}$. Afirmamos que

$$\forall \sigma,\tau\in\mbox{\it Ent\/}^*:\ (\sigma R \tau)\Leftrightarrow (\sigma\equiv_L \tau)$$ (47)

En efecto, si $\sigma R \tau$ entonces, $\forall\upsilon\in\mbox{\it Ent\/}^*$, al ser R congruente por la derecha, $\sigma\upsilon R \tau\upsilon$. Como L es la unión de algunas clases de R, esto da que $\left(\sigma\cdot\upsilon\in L\Leftrightarrow \tau\cdot\upsilon\in L\right)$. Así pues, $\sigma\equiv_L \tau$. De la relación 4.36 vemos que toda clase de equivalencia respecto a ``$\equiv_L$'' es la unión de clases de equivalencia respecto a R. Por tanto el índice de ``$\equiv_L$'' no puede exceder el de R. Como este último es finito el de ``$\equiv_L$'' es también finito.

$3. \Rightarrow 1.$ ``$\equiv_L$'' es una relación de equivalencia de índice finito, congruente por la derecha. Definamos $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ haciendo $Q=\mbox{\it Ent\/}^*/\equiv_L$, $q_0=[\mbox{\it nil\/}]$, $F=\{[\sigma]\vert\sigma\in L\}$ y $\mbox{\it tran\/}:([\sigma],e)\mapsto [\sigma e]$. Es evidente que una palabra es reconocida por $\mbox{\it AF\/}$ si y sólo si esa palabra está en L. Así pues, $L=L(\mbox{\it AF\/})$ y,consecuentemente, es regular.


Para un autómata finito $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ diremos que dos estados $q_1,q_2\in Q$ son indistinguibles si para cualquier palabra $\sigma \in \mbox{\it Ent\/}^*$,

$$\mbox{\it tran\/}^*(q_1,\sigma)\in F\Leftrightarrow \mbox{\it tran\/}^*(q_2,\sigma)\in F.$$

Si dos estados $q_1,q_2\in Q$ no fueran indistinguibles, entonces habría una palabra $\sigma \in \mbox{\it Ent\/}^*$ tal que

$$(\mbox{\it tran\/}^*(q_1,\sigma),\mbox{\it tran\/}^*(q_2,\sigma)\in (F\times (Q-F))\cup((Q-F)\times F).$$

Diremos que tal palabra distingue a los estados q₁,q₂. La relación de indistinguibilidad es una relación de equivalencia. La denotaremos como ``$\equiv_I$''. Sea $L=L(\mbox{\it AF\/})$ el lenguaje reconocido por el autómata $\mbox{\it AF\/}$. Para cualesquiera dos palabras $\sigma,\tau\in\mbox{\it Ent\/}^*$ rige la equivalencia siguiente

$$[T(\sigma)\equiv_I T(\tau)]\Leftrightarrow [\sigma\equiv_L \tau].$$

Por tanto el autómata $\mbox{\it AFM\/}_L=\left(\mbox{\it Ent\/}^*/\equiv_L\right)$ construído en la demostración de la implicación $(3. \Rightarrow 1.)$ del teorema de Myhill-Nerode 4.6.1 es isomorfo al autómata cociente $\mbox{\it AFM\/}_I=\left(Q^{\mbox{\scriptsize\it con}}/\equiv_I\right)$ y, por consiguiente, es una imagen homomorfa de la parte conexa del autómata $\mbox{\it AF\/}$, $h:T(\sigma)\mapsto [\sigma]$ es un homomorfismo. De hecho, $\mbox{\it AFM\/}_L$ es una imagen homomorfa de cualquier autómata que reconozca a L. Así pues, resulta de inmediato la

Proposición 6.2   El autómata mínimo que reconoce a un lenguaje regular L es $\mbox{\it AFM\/}_L=\left(\mbox{\it Ent\/}^*/\equiv_L\right)$.

El cálculo de $\mbox{\it AFM\/}_L$ es equivalente al cálculo de $\mbox{\it AFM\/}_I$, es decir, al cálculo de clases de estados indistinguibles en Q. Para esto observemos lo siguiente:

1.

Para una pareja q₁ y q₂, si en cada símbolo $e\in\mbox{\it Ent\/}$ la pareja $\{\mbox{\it tran\/}(q_1,e),\mbox{\it tran\/}(q_2,e)\}$ consta de estados indistinguibles entonces $\{q_1,q_2\}$ es de indistinguibles también.

2.

De manera recíproca, si $\sigma$ distingue a la pareja $\{\mbox{\it tran\/}(q_1,e),\mbox{\it tran\/}(q_2,e)\}$ entonces $e\sigma$ distingue a la pareja $\{q_1,q_2\}$.

Así pues, para calcular las clases de estados ``distinguibles'' podemos proceder como sigue:

1.

Inicialmente consideremos vacías las listas de parejas distinguibles y de parejas marcadas. Para cada pareja de estados distintos $\{q_1,q_2\}$, consideremos una lista vacía de parejas asociadas a esa pareja.

2.

Para cada $q_1\in F$ y $q_2\not\in F$ incluyamos la pareja $\{q_1,q_2\}$ tanto en la lista de distinguibles, pues los estados lo son con la palabra vacía $\mbox{\it nil\/}$, como en la de marcadas.

3.

Para cada pareja $\{q_1,q_2\}$ que no haya sido marcada,

(a)

para cada símbolo de entrada $e\in\mbox{\it Ent\/}$,

i.

si $\{\mbox{\it tran\/}(q_1,e),\mbox{\it tran\/}(q_2,e)\}$ es distinguible, digamos con la palabra $\sigma$, entonces incluyamos la pareja $\{q_1,q_2\}$ en la lista de distinguibles, pues lo es con la palabra $e\sigma$, e incluyamos a todas las parejas asociadas a $\{q_1,q_2\}$ en la lista de distinguibles, con indicadores a sus correspondientes palabras que los distinguen,

ii.

en otro caso, asociemos la pareja actual $\{q_1,q_2\}$ a la pareja $\{\mbox{\it tran\/}(q_1,e),\mbox{\it tran\/}(q_2,e)\}$, siempre que esta última conste de dos estados distintos,

(b)

coloquemos a la pareja actual $\{q_1,q_2\}$ en la lista de palabras marcadas.

4.

Las parejas que no son distinguibles dan las clases de estados indistinguibles.

Siguiente: Lema de bombeo Un nivel arriba: Expresiones regulares Anterior: PB visto como un