Proving a class of languages is closed under union when it closed under concatenation, (inverse) homomorphic images, and intersections.

computer scienceformal-languageslogicregular-languagesemigroup-homomorphism

Let $C$ be a class of languages closed under concatenation ($\cdot$), intersection, homomorphic images, inverse homomorphic images, and intersection with regular languages. Prove that $C$ is also closed under union.

My attempt: Let $L_1, L_2 \in C$. Let $\square_1, \square_2$ be two unique elements not in $L_1, L_2$ respectively. Then $L_i \cup \{\square_i\}$ is an inverse homomorphic image of $L_i$. But then $L_i \cup \{\epsilon\}$ is a homomorphic image of $L_i\cup \{\square_i\}$. So $L_1\cup L_2 \subseteq (L_1\cup \{\epsilon\})\cdot (L_2\cup \{\epsilon\}) \in C$. However, I am not sure how to go from $(L_1\cup \{\epsilon\})\cdot (L_2\cup \{\epsilon\})$ to $L_1\cup L_2 \in C$. I have not used intersections at all, so I think I'm on the wrong track.

Best Answer

If $C$ is empty, then $C$ is closed under union and we are done. If $C=\{\emptyset\}$, then $C$ is closed under union and we are done.

Assume $C$ contains one nonempty language.

Let $P\in C$ be nonempty. Let $\zeta$ be the homomorphism that maps every letter to $\epsilon$, the empty string. $\zeta$ maps every string to $\epsilon$ as well. So $\zeta(P)=\{\epsilon\}$. Hence $\{\epsilon\}\in C$.

Suppose $L_1, L_2\in C$. I assume that you have shown $L_1\cup\{\epsilon\}\in C$ as well as $L_2\cup\{\epsilon\}\in C$.

Let $\alpha, \beta$ be two letters that never appear in any word in $L_1$ nor in any word in $L_2$. We have

$$L_1\cup L_2\cup\{\epsilon\}=g_{\alpha\beta}(\left((\cdot\alpha)^*\cup(\cdot\beta)^*\right)\cap f_\alpha(L_1\cup\{\epsilon\})f_\beta(L_2\cup\{\epsilon\}))$$

where

  • $f_\alpha$ maps every letter $\sigma$ to $\sigma\alpha$.
  • $f_\beta$ maps every letter $\sigma$ to $\sigma\beta$.
  • $f_\alpha(L_1\cup\{\epsilon\})f_\beta(L_2\cup\{\epsilon\})$ is the concatenation of $f_\alpha(L_1\cup\{\epsilon\})$ and $f_\beta(L_2\cup\{\epsilon\})$.
  • $(\cdot\alpha)^*$ is the regular language that consists of all words of even length such that each letter at an even position is $\alpha$.
  • $(\cdot\beta)^*$ is the regular language that consists of all words of even length such that each letter at an even position is $\beta$.
  • $g_{\alpha\beta}$ is the homomorphism that maps every letter to itself except that it maps $\alpha$ and $\beta$ to the empty string.

Hence $L_1\cup L_2\cup\{\epsilon\}\in C$.

If $\epsilon\in L_1\cup L_2$, then $L_1\cup L_2=L_1\cup L_2\cup\{\epsilon\}\in C$.
Otherwise, $\epsilon\notin L_1\cup L_2$, then $L_1\cup L_2=(L_1\cup L_2\cup\{\epsilon\})\cap(\Sigma^*\setminus\{\epsilon\})\in C$, where $\Sigma$ is the set of all letters that ever appear in $L_1$ or $L_2$.

Related Question