Seja
um alfabeto e sejam
e
subconjuntos de
, com
. Mostre que
.
Passo 1
O enunciado pede para mostrar que, se temos dois conjuntos de palavras
e
sobre um alfabeto
com
, então a estrela de Kleene de
fica contida na estrela de Kleene de
. O conteúdo principal é a definição de fechamento de Kleene:
Passo 2
Vamos mostrar que para todo
vale
Feito isso, como a união de subconjuntos é subconjunto da união correspondente, teremos
.
Passo 3
Base da indução
: por definição
e
. Logo
Passo 4
Passo indutivo: suponha que, para algum
, já temos
Queremos mostrar
. Tome
. Pela definição de produto de linguagens, existe
e
tais que
.
Pelo hipótese de indução e, como
, temos
.
Logo . Assim
.
Pelo hipótese de indução
Logo
Passo 5
Concluímos por indução que
Então, passando para a união em
,