Mostre que estas igualdades são válidas.
para todo conjunto
de seqüências.
Passo 1
O enunciado pede para mostrar que, para todo conjunto
(onde
é um alfabeto e
o conjunto de todas as cadeias finitas), vale a igualdade
Aqui o conteúdo é a operação Kleene star em teoria de linguagens formais, que gera todas as concatenações finitas de cadeias de um dado conjunto.
Passo 2
Mostramos primeiro
. Seja
. Por definição de estrela, existem
e cadeias
tais que
Cada
é, por sua vez, concatenação finita de cadeias de
. Ou seja, para cada
existe
e
Logo
que é uma concatenação finita de cadeias em
. Assim
. Concluímos
.
Passo 3
Agora mostramos
. Seja
. Então, por definição,
é uma concatenação finita de cadeias em
. Mas também isso significa que
é (trivialmente) concatenação de um único elemento de
, a saber de si próprio. Portanto
pode ser visto como
logo
. Assim
.