0
$\begingroup$

so for a homework assignment i need to prove the following:

We have arbitrary languages L1⊆∑1*, L2⊆∑2*, L3⊆∑3*, L4⊆∑4*

Prove that the followging is either true or false:

If L1 ∪ L2 ⊆ L3 ∩ L4, then L1◦L2 ⊆ L3◦L4 (◦ = concatenation)

Now i know this is true, but i don't know how to approach this problem...

Any tips on pointing me into the right direction are appreciated!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The assignment tests basic definitions (and some elementary set theory).

As you know, for arbitrary $L_1,L_2$, you have $L_1\cdot L_2 = \{ x\cdot y \mid x\in L_1, y\in L_2\}$.

Now if $L_1\subseteq L_3$ and $L_2\subseteq L_4$ then $L_1\cdot L_2 \subseteq L_3\cdot L_4$. This is rather clear, or if you want, can shown with elementary steps. Take any $z\in L_1\cdot L_2$, then $z=xy$ for $x\in L_1$ and $y\in L_2$. However, because of the inclusions, $z=xy$ for $x\in L_3$ and $y\in L_4$, thus $z\in L_3 \cdot L_4$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yeah i get this, but the only information i have is --> L1 ∪ L2 ⊆ L3 ∩ L4 How would i use this for showing that e.g. L1⊆L3 and L2⊆L4 $\endgroup$
    – GSerum_
    Apr 30, 2018 at 15:14
  • $\begingroup$ That is basic set theory, and is not particular tolanguages. For example $A\subseteq B\cap C$ if and only if $A\subseteq B$ and $A\subseteq C$. $\endgroup$
    – Hendrik Jan
    May 1, 2018 at 23:38

Your Answer

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

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