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.

Exercise. Let \( \Sigma \) be an alphabet and \( w \) a string over \( \Sigma \). We define the string reversal of \( w \in \Sigma^* \), denoted \( w^R \), as the reverse of the string \( w \). Formally, this operation can be defined by induction: \[ \begin{aligned} \text{Base Case: } & \varepsilon^R = \varepsilon \\ \text{Inductive Step: } & \text{for } a \in \Sigma,\ w \in \Sigma^*,\ (w \cdot a)^R = a \cdot w^R \end{aligned} \] a) Let \( \Sigma = \{a, b\} \) and \( w = ab \), \( v = ba \). What is \( (w^2 v^2 w^0)^R \)?

b) Prove by induction that \[ (w \cdot v)^R = v^R \cdot w^R. \]

Exercise. Given \( \Sigma = \{a, b\} \), \( L_1 = \{a, ab, abab\} \), \( L_2 = \{(ab)^n : n \in \mathbb{N}\} \).

What is the result of the following language operations?

1. \( L_1 \cup L_2 \)
2. \( L_1 \cap L_2 \)
3. \( L_1 - L_2 \)
4. \( L_2 - L_1 \)

Exercise. Given \( \Sigma = \{a, b\} \) and \( L_1 = \{a, ab, abab\} \). How many strings of length 0, 1, and 2 are there in \( L_1^* \)?

Exercise. Given \( \Sigma = \{a, b\} \), \( L_1 = \{a^n : n \in \mathbb{N}\} \), \( L_2 = \{b^n : n \in \mathbb{N}\} \).

What is the result of the following language operations?

1. \( L_1 \cdot L_2 \)
2. \( (L_1)^2 \cdot (L_2)^2 \)
3. \( L_1^* \cdot L_2^* \)

Exercise. Given \( \Sigma = \{0\} \) and \( L \subset \Sigma^* \). Are the following statements true or false?

1. If \( L \) is finite and \( n \in \mathbb{N} \), \( n \geq 2 \), then \( |L^n| = |L|^n \).
2. If \( L \) is finite then \( |L^*| = |\mathbb{N}| \).

Exercise. Let \( \Sigma = \{a, b\} \) be an alphabet and let \( L_1, L_2 \subseteq \Sigma^* \) be languages. Find particular examples for \( L_1 \) and \( L_2 \) such that the following statements are satisfied.

1. \( L_1^0 = \{\varepsilon\} \)
2. \( |L_1 \cup L_1^2| = |L_1| + |L_1|^2 \)
3. \( L_1 \subseteq L_2 \ \text{and}\ L_1 \cdot L_2 = L_2 \cdot L_1 \)
4. \( L_1 \cdot L_2 = L_1 \)
5. \( |L_1 \cdot L_2| = |L_1 \times L_2| \)