Languages

Exercise (Sipser). Prove that \(L^2 \subseteq L\) iff \(L = L^+\). This is a good exercise to both practice your proving skills and get familiar with language operations.

This is only a partial solution to give you a hint. Since this statement is an if and only if, you must prove both directions.

\(\Rightarrow\) Assume \(L^2 \subseteq L\). You must show that \(L^+ = L\). Recall the definition of \(L^+ = L \cup L^2 \cup \dots = \bigcup_{i=1}^{\infty} L^i\). The hint for this direction is to show that for any \(n \geq 2, L^n \subseteq L\). You can prove this by induction on \(n\). Once you've shown this, the main result should follow easily.

\(\Leftarrow\) Follows almost entirely by definition.

Exercise. Suppose \(A\) and \(B\) are two languages defined over a non-empty alphabet \(\Sigma\). Prove that if both languages are finite \(|A \times B| = |A| \times |B|\). Is the same true for language concatenation?

Hint: For the first question, you can use a counting argument to show this directly. For the second question, that same counting argument breaks down. Try to see why.