Seja V um alfabeto e sejam A e B subconjuntos de V^{*}, com A \subseteq B. Mostre que A^{*} \subseteq B^{*}.

Passo 1

O enunciado pede para mostrar que, se temos dois conjuntos de palavras A e B sobre um alfabeto V com A \subseteq B, então a estrela de Kleene de A fica contida na estrela de Kleene de B. O conteúdo principal é a definição de fechamento de Kleene:
A^* \;=\;\bigcup_{n=0}^{\infty}A^n,
B^* \;=\;\bigcup_{n=0}^{\infty}B^n.

Passo 2

Vamos mostrar que para todo n\ge0 vale
A^n \subseteq B^n.
Feito isso, como a união de subconjuntos é subconjunto da união correspondente, teremos A^*\subseteq B^*.

Passo 3

Base da indução n=0: por definição A^0 = \{\varepsilon\} e B^0 = \{\varepsilon\}. Logo
A^0 = B^0 \quad\implies\quad A^0 \subseteq B^0.

Passo 4

Passo indutivo: suponha que, para algum n\ge0, já temos
A^n \subseteq B^n.
Queremos mostrar A^{n+1} \subseteq B^{n+1}. Tome w \in A^{n+1}. Pela definição de produto de linguagens, existe \,u\in A^n e v\in A tais que w = uv.
Pelo hipótese de indução u\in B^n e, como A\subseteq B, temos v\in B.
Logo w = uv\in B^n\,B = B^{n+1}. Assim A^{n+1}\subseteq B^{n+1}.

Passo 5

Concluímos por indução que
\forall\,n\ge0:\quad A^n \subseteq B^n.
Então, passando para a união em n,
A^* = \bigcup_{n=0}^\infty A^n \;\subseteq\; \bigcup_{n=0}^\infty B^n = B^*.

Resposta

\displaystyle A^* \subseteq B^*

Exercícios de Livros Relacionados