Sea
un alfabeto. Para dos lenguajes cualesquiera
definimos
Denotemos por
al conjunto de ``partes'' de ,
es decir, a la colección de todos los lenguajes sobre el alfabeto .
A algunos lenguajes particulares se los distingue desde la manera en la que se los denota. Algunos de éstos son los siguientes:
Proposición 1.1
La estructura algebraica
posee las propiedades siguientes:
(12)
Además se cumplen también las propiedades siguientes:
Producto
(13)
Suma
(14)
La verificación de las relaciones anteriores es rutinaria.
Tenemos pues que
tiene una estructura de semianillo, idempotente respecto a la adición.
Proposición 1.2 (Operación estrella)
En
se cumplen las relaciones siguientes:
K*
=
(15)
=
(16)
=
(17)
(KL)*K
=
K(LK)*
(18)
(K+L)*
=
(K*L)*K*
(19)
(KL)*
=
(20)
=
K*
(21)
=
K*
(22)
(K*)*
=
K*
(23)
=
(24)
K*K*
=
K*
(25)
En efecto, la ecuación (4.4) se sigue de las ecuaciones siguientes:
La ecuación (4.5) se sigue al reiterar la ecuación (4.4).
La ecuación (4.6) se sigue de la ecuación (4.4) y de la condición de nulidad (4.2).
La ecuación (4.7) se sigue al desarrollar como sumas cada uno de sus miembros para ver que ambas constan de sumandos de la forma
K(LK)i=(KL)iK con .
La ecuación (4.8) se sigue al desarrollar como sumas cada uno de sus miembros para ver que todo sumando en una suma aparece en la otra.
La ecuación (4.9) se sigue de las ecuaciones (4.4) y (4.7).
La ecuación (4.10) se sigue de la ecuación (4.4) y de que
es una unidad multiplicativa, (ec's. 4.1).
La ecuación (4.11) se sigue de la ecuación (4.4) y de la idempotencia, (ec. 4.3).
La ecuación (4.12) se sigue de las siguientes ecuaciones, justificadas ya anteriormente:
pues la igualdad (1) es una forma de la ec. (4.4), la igualdad (2) lo es de la ec. (4.8), la igualdad (3) lo es de la ec. (4.10), la igualdad (4) lo es de la ec. (4.4), la igualdad (5) lo es de la ec. (4.3) y la igualdad (6) lo es de la ec. (4.4).
La ecuación (4.13) se sigue de la ecuación (4.12) y de la ecuación (4.6) al tomar
.
La ecuación (4.14) se sigue de las siguientes ecuaciones, justificadas ya anteriormente:
pues la igualdad (1) es una forma de la ec. (4.10), la igualdad (2) lo es de la ec. (4.8), la igualdad (3) lo es de que
es unidad multiplicativa y la igualdad (4) lo es de la ec. (4.12).
Diremos que un lenguaje
posee la condición de la palabra vacía (CPV) si
.
Lema 1.1
Sea K un lenguaje que no posee la CPV. Las siguientes dos condiciones se cumplen, cualesquiera que sean los lenguajes L y X:
:
(26)
:
(27)
En efecto, para la primera implicación, supongamos que
,
y sea
su longitud. Sea n>m. Puesto que
,
necesariamente
,
pero todas las palabras de KnK* son de longitud estrictamente mayor que la de ,
pues K no posee la CPV, por tanto a fortiori
.
Así pues,
y K*+L=L.
Ahora, para la segunda implicación, si se supone que X=KX+L entonces, al reiterar esta ecuación, resulta
.
Sea
,
y sea
.
Bajo esta condición, rigen las siguientes equivalencias:
Por tanto, X=K*L.
Ahora bien, la relación de inclusión define un ``orden parcial'' en la clase
,
y es tal que para cualesquiera dos lenguajes
:
Así pues, atendiendo únicamente a las operaciones definidas arriba se tiene que la relación