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^+$

  • 2
    $\begingroup$ 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^+$. $\endgroup$ – David Richerby Mar 12 '18 at 10:35
  • $\begingroup$ 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. $\endgroup$ – Kong Mar 12 '18 at 10:41
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Mar 12 '18 at 10:46

It is just a simple subset proof:

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^+$.

  • $\begingroup$ Thanks Nick ! I rewrote your answer in a more explicit form to verify my doubts. I was hoping you could take a quick look above and see if I did anything wrong (I dont think I did). $\endgroup$ – Kong Mar 12 '18 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.