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 R_L que induce el lenguaje L se define como sigue:

$$\forall \sigma_1,\sigma_2\in\Sigma^*:\ \sigma_1R_L\sigma_2\;\... ...ma^*(\sigma_1\sigma\in L\Leftrightarrow\sigma_2\sigma\in L).$$ (1)

Es decir, dos palabras están relacionada según R_L 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 R_L es una relación de equivalencia. De hecho, es una congruencia derecha pues rige la implicación:

$$\forall \sigma_1,\sigma_2\in\Sigma^*:\ \sigma_1R_L\sigma_2\;\... ...\; \forall \sigma\in\Sigma^*(\sigma_1\sigma R_L\sigma_2\sigma).$$

El índice del lenguaje L es, por definición, el índice de la relación R_L. 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.