# Does complement distribute over concatenation?

Prove or disprove

$\exists L_{1},L_{2}\subseteq\Sigma^{*}:\quad L_{1}\ne L_{2}\wedge\overline{L_{1}\cdot L_{2}}=\overline{L_{1}}\cdot\overline{L_{2}}$

Where $\cdot$ means concatenation, and over line is complement. Also, Let $\Sigma=\{a,b\}$.

• Step one: translate the formula to natural language and adapt the title. Step two: what have you tried and where did you get stuck? Commented Mar 11, 2015 at 14:49
• What Raphael was saying was that question titles consisting of all or mostly LaTeX are difficult for search engines to handle well. Since one function of this site is to work towards an archive of questions and answers, it will be difficult for later users to discover your question. Commented Mar 12, 2015 at 14:51
• Motivated by @Raphael's comment, I edited the title. Feel free to modify it if you have a better one. Commented May 21, 2015 at 16:08

It is possible. Hint: Let $L_1=a^*, L_2=\Sigma^*$. Fill in the details.
Try first very simple languages, such as $\emptyset$, $\Sigma^*$, or $\{a\}$. If they don't work out, try more complex ones that fix the 'flaws' the simple languages had.
• But: In this case, it is possible, though you've stated so far that it isn't. Consider the two languages $\emptyset$ and $\{a\}$. Can you give a string $w$ what is in $\overline{L_{1}\cdot L_{2}}$, but not in $\overline{L_{1}}\cdot\overline{L_{2}}$ - or vice versa? Commented Mar 11, 2015 at 18:37
• @AstroNauft to give another hint: What are the results of the computations $\emptyset \cdot \{ a \}$, and $\overline{\emptyset}$? Commented Mar 12, 2015 at 8:27