3
$\begingroup$

I know this is an amateur question but is it true to say that for any three nonempty languages $L_{1},L_{2},L_{3}$ over an alphabet $\Sigma$ we have $L_{1}(L_{2} \cap L_{3}) = L_{1}L_{2} \cap L_{1}L_{3}$ if and only if $L_{2} \subseteq L_{3}$ or $L_{3} \subseteq L_{2}$? Some theorems in mathematics lead me ask this. If not, what is the necessary and sufficient condition for the equality to hold?

$\endgroup$
5
  • 1
    $\begingroup$ The condition has to depend on $L_1$, since if $L_1=\emptyset$ then the equality trivially holds for any two sets $L_2,L_3$. $\endgroup$
    – nir shahar
    Sep 25, 2021 at 15:35
  • $\begingroup$ @nirshahar What if we consider the languages to be nonempty? Is there actually any necessary and sufficient condition? $\endgroup$
    – Emad
    Sep 25, 2021 at 15:40
  • 2
    $\begingroup$ Another case: $L_1=(L_2\cup L_3)^*$. Or $L_1=\Sigma^*$. What mathematical theorems having to do with concatenation are you thinking of? $\endgroup$
    – rici
    Sep 25, 2021 at 18:37
  • $\begingroup$ @rici There are a few (to some extent) similar theorems about vectors spaces, groups, etc: Like the union of two subspaces is a subspace if and only if one is contained in the other. I saw one direction is correct, so I made the guess. $\endgroup$
    – Emad
    Sep 25, 2021 at 18:50
  • $\begingroup$ @rici Also one other thing is that we have a monoid here so it's natural for these ideas to strike the mind. $\endgroup$
    – Emad
    Sep 25, 2021 at 18:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.