# Combination of two Languages in a arbitrary complexity class

Given two unrelated languages $$L_0$$ and $$L_1$$ contained in some complexity class $$C$$. Is the language $$L_x=L_0\times L_1= \{(x,y)|x\in L_0, y\in L_1\}$$ always contained in $$C$$?

And if that is the case, can we just extend this recursively and create a single language $$(L_{All})$$ from all other languages contained in $$C$$ (even if the count of languages in $$C$$ is infinite)? Is the language $$L_{All}$$ always contained in $$C$$ as well?

• You will have to explain what "extending this recursively" would mean - how would you extend recursively? Do you start from two languages $L_0,L_1$ and construct $L_2:=L_0\times L_1$, and then $L_3:=L_1\times L_2$, and so on with the recurrence formula of $L_{n+2}=L_n\times L_{n+1}$ ? Is this the process you have in your mind? Jan 4 at 16:38
• The answer depends on the class $C$. Jan 4 at 16:43
• @nirshahar yes. Exactly. Jan 4 at 17:34
• @YuvalFilmus i understand/agree. I was reffering to the english meaning. I guess I should have used 'arbitrary' or something similar. Jan 4 at 17:36

The answer depends on the class $$C$$. Many classes will be closed under your operation, but some are not. For example, DCFL, the class of all deterministic context-free language, is not. To show this, we slightly adapt the counterexample in this answer. Define $$L_A = \{ a^i b^j c^k : i \neq j \}; L_B = \{ a^i b^j c^k : j \neq k \}; L_1 = \{ ,w : w \in L_A \} \cup L_B; L_0 = \; ,^*$$ The languages $$L_0$$ and $$L_1$$ are both DCFL. Let $$L_x = L_0 \times L_1$$ be their product. Suppose that $$L_x$$ were DCFL. Then so would $$L_y = \{ w : (w) \in L_x \}$$ be, since DCFL is closed under quotient. Since DCFL is closed under intersection with a regular language, $$L_z = L_y \cap \, ,,(a+b+c)^*$$ would be DCFL. Notice that $$L_z = \, ,, (L_A \cup L_B)$$. Again using closure under quotient, it would follow that $$L_A \cup L_B$$ is DCFL, but that is known to be false.
• Thanks a lot. I am still trying to understand the counterexample. Assuming the class $C$ is the class i.e. $\Sigma_2^P$ in the second level of the polynomial hierarchy. Is that one closed under the above criteria? Jan 4 at 17:40
• I understand. But for the specific case of $\Sigma_2^P$ any pointers how to figure it out? Jan 4 at 17:47