Question 1.23: Let B be any language over the alphabet Σ. Prove that B = B^...
Let B be any language over the alphabet Σ. Prove that B=B^{+} iff BB\subseteq B.
We prove both directions of the “iff.”
(→) Assume that B=B^{+} and show that BB\subseteq B.
For every language BB\subseteq B^{+} holds, so if B=B^{+}, then BB\subseteq B.
( ←) Assume that B=B^{+} and show that B=B^{+}.
For every language B\subseteq B^{+}, so we need to show only B^{+}\subseteq B. If \omega \in B^{+}, then \omega = x_{1}x_{2} …x_{k} where each x_{i}\in B and k \geq 1. Because x_{1},x_{2}\in B and BB\subseteq B, we have x_{1}x_{2}\in B. Similarly, because x_{1}x_{2} is in B and x_{3} is in B, we
have x_{1}x_{2}x_{3}\in B. Continuing in this way, x_{1} …x_{k}\in B. Hence \omega \in B, and so we may conclude that B^{+} \subseteq B.
The latter argument may be written formally as the following proof by induction.
Assume that BB \subseteq B.
Claim: For each k\geq 1, if x_{1}, …,x_{k}\in B, then x_{1}…x_{k}\in B .
Basis: Prove for k=1. This statement is obviously true.
Induction step: For each k\geq 1, assume that the claim is true for k and prove it to be true for k + 1.
If x_{1},…,x_{k},x_{k+1} \in B, then by the induction assumption, x_{1}…x_{k+1} \in B. There-fore x_{1}…x_{k} x_{k+1} \in BB, but BB\subseteq B, so x_{1}…x_{k+1}\in B. That proves the induction step and the claim. The claim implies that if BB\subseteq B, then B^{+}\subseteq B .