next up previous contents
Siguiente: Algunas variantes Un nivel arriba: Particiones en base a Anterior: Particiones en base a

Congruencia lateral inducida por un lenguaje

Sea $\Sigma$ un alfabeto. Construimos en esta sección una relación de congruencia lateral en $\Sigma^*$ que utilizaremos frecuentemente en este curso. Sea L un lenguaje de $\Sigma^*$. La relación RL que induce el lenguaje L se define como sigue:

 \begin{displaymath}\forall \sigma_1,\sigma_2\in\Sigma^*:\ \sigma_1R_L\sigma_2\;\...
...ma^*(\sigma_1\sigma\in L\Leftrightarrow\sigma_2\sigma\in L).
\end{displaymath} (1)

Es decir, dos palabras están relacionada según RL si y sólo si, al añadírseles un mismo sufijo, o bien ambas palabras resultantes quedan en el lenguaje, o bien ambas dejan de pertenecer al lenguaje. Es fácil ver que RL es una relación de equivalencia. De hecho, es una congruencia derecha pues rige la implicación:

\begin{displaymath}\forall \sigma_1,\sigma_2\in\Sigma^*:\ \sigma_1R_L\sigma_2\;\...
...\; \forall \sigma\in\Sigma^*(\sigma_1\sigma R_L\sigma_2\sigma).\end{displaymath}

El índice del lenguaje L es, por definición, el índice de la relación RL. La noción de índice es de particular importancia para analizar la complejidad del lenguaje. El Teorema de Myhill-Nerode, que veremos más adelante, asevera que un lenguaje será regular si y sólo si es de índice finito.

Guillermo Morales-Luna
2000-06-27