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\}$.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Step one: translate the formula to natural language and adapt the title. Step two: what have you tried and where did you get stuck? $\endgroup$– RaphaelCommented Mar 11, 2015 at 14:49
-
$\begingroup$ 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. $\endgroup$– Rick DeckerCommented Mar 12, 2015 at 14:51
-
$\begingroup$ Motivated by @Raphael's comment, I edited the title. Feel free to modify it if you have a better one. $\endgroup$– Rick DeckerCommented May 21, 2015 at 16:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
It is possible. Hint: Let $L_1=a^*, L_2=\Sigma^*$. Fill in the details.
answered Mar 11, 2015 at 15:34
$\begingroup$
$\endgroup$
3
A good starting point is to try to find languages and apply them to your formula, in attempt to satisfy it.
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.
If it feels impossible to find languages that satisfy the formula, it might just be impossible.
-
$\begingroup$ I think it's impossible. In that case, I need to prove it's impossible. $\endgroup$ Commented Mar 11, 2015 at 14:20
-
$\begingroup$ 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? $\endgroup$– Mike B.Commented Mar 11, 2015 at 18:37
-
$\begingroup$ @AstroNauft to give another hint: What are the results of the computations $\emptyset \cdot \{ a \}$, and $\overline{\emptyset}$? $\endgroup$– Mike B.Commented Mar 12, 2015 at 8:27