# Show that the regular language is contained in another

Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ? $\bigotimes$ denote the transducer cross product.

$L_1^+ \bigotimes L_2^+$ contains $(L_1 \bigotimes L_2)^+$

============================================================================

Thanks PHPNick. Would my version (rewritten from yours) be correct ? I am just trying to make it more explicit to verify my doubts. If my understanding of the cross product and the + operator is correct.

Let $L_1$ and $L_2$ be the following

$L_1 = \{u_1,u_2,u_3\}$ $L_2 = \{v_1,v_2,v_3\}$

Then $L_1^+$ and $L_2^+$ would be the set of all strings that can be made by concatenating finitely many (and at least one) strings (corrected by David Richerby)

$L_1^+ = \{u_1,u_1u_1,u_1u_1u_1,...,u_2,...,u_3,..., u_1u_2,u_1u_2u_1,\dots\}$

$L_2^+ = \{v_1,v_1v_1,v_1v_1v_1,...,v_2,...,v_3,..., v_1v_2,v_1v_2v_1,\dots\}$

The two sets defined in the question are thus

$L_1^+ \bigotimes L_2^+ = \{ (u_1,v_1), (u_1,v_1v_1), \dots, (u_1u_1,v_1), \dots, (u_1u_1,v_1v_1), \dots \}$ $(L_1 \bigotimes L_2)^+ = \{ (u_1,v_1), (u_1,v_2), (u_1,v_3), \dots, (u_2,v_1), \dots \}$

The set $L_1^+ \bigotimes L_2^+$ thus contains $(L_1 \bigotimes L_2)^+$ because we can see that $(u_1,v_1), (u_1,v_2)$ etc are present in $L_1^+ \bigotimes L_2^+$

• No, $L^+$ is the set of all strings that can be made by concatenating finitely many (and at least one) strings from $L$. That is, writing $L^k = \{w_1\dots w_k\mid w_1, \dots, w_k\in L\}$, $L^+ = L \cup L^2 \cup L^3 \cup\cdots$. E.g., $u_1u_2u_1\in L_1^+$. – David Richerby Mar 12 '18 at 10:35
• Thanks ! And the remaining lines would still be correct ? Question: How do I concatenate elements for the expression $(L_1 \bigotimes L_2)^+$ because it has the brackets to each of its element. The elements I wrote for that expression do not have any concatenated ones. – Kong Mar 12 '18 at 10:41
• Sorry, but this site isn't suited to back-and-forth discussion or to grading answers. You should ask your professor or TA, or somebody in your class who's more confident with the material than you are. Also, I've already told you that I don't know what $\otimes$ means but you never did provide a definition. – David Richerby Mar 12 '18 at 10:46

Let $(u, v) \in (L_1 \otimes L_2)^+$. Thus, there is a decomposition of $(u, v)$ into $(u_1 \ldots u_k, v_1 \ldots v_k)$ with $u_i \in L_1$ and $v_i \in L_2$ and $k > 0$. Hence, we have $u \in L_1^+, v \in L_2^+$. So overall we have $(u, v) \in L_1^+ \otimes L_2^+$.