Siguiente: Propiedades de cerradura Un nivel arriba: Particiones en base a Anterior: Congruencia lateral inducida por

Algunas variantes

Sea $\Sigma$ un alfabeto, L un lenguaje de $\Sigma^*$ y sea k>0. La relación R_L,k se define como sigue:

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

Es decir, dos palabras están relacionada según R_L,k si y sólo si, al añadírseles un mismo sufijo de longitud a lo sumo k, o bien ambas palabras resultantes quedan en el lenguaje, o bien ambas dejan de pertenecer al lenguaje. Es fácil ver que R_L,k es una relación de equivalencia, aunque no es una congruencia. Esta relación puede ser de índice finito, sin que ello implique que el lenguaje L sea regular.