patternMinor
Concatenation of the intersection of two languages
Viewed 0 times
thelanguagestwointersectionconcatenation
Problem
I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings:
$$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$
I've tried a lot of sets for e.g.
$L1 = \{a,b,c,d\}$,
$L2 = \{a,f,g\}$,
$L3 = \{s,d,h\}$.
but always the LHS comes out equal to the RHS instead of unequal.
Any idea how to prove this?
$$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$
I've tried a lot of sets for e.g.
$L1 = \{a,b,c,d\}$,
$L2 = \{a,f,g\}$,
$L3 = \{s,d,h\}$.
but always the LHS comes out equal to the RHS instead of unequal.
Any idea how to prove this?
Solution
First, you may notice that there is a one-sided containment here. It always holds that
$(L_1\cap L_2)L_3\subseteq L_1L_3\cap L_2L_3$ (prove it!)
From this, you see that in order for the equality to fail, you need to get a strict containment.
Intuitively, this means that you need the concatenation with $L_3$ to add words to both $L_1$ and $L_2$.
One way to achieve this is, for example, to first let $L_1\cap L_2=\emptyset$, and then "tailor" $L_3$ to fix this emptiness.
A concrete example is below (hidden as spoiler, hover mouse to see it):
$L_1=\{a\}$, $L_2=\{aa\}$, $L_3=\{a,\epsilon\}$.
$(L_1\cap L_2)L_3\subseteq L_1L_3\cap L_2L_3$ (prove it!)
From this, you see that in order for the equality to fail, you need to get a strict containment.
Intuitively, this means that you need the concatenation with $L_3$ to add words to both $L_1$ and $L_2$.
One way to achieve this is, for example, to first let $L_1\cap L_2=\emptyset$, and then "tailor" $L_3$ to fix this emptiness.
A concrete example is below (hidden as spoiler, hover mouse to see it):
$L_1=\{a\}$, $L_2=\{aa\}$, $L_3=\{a,\epsilon\}$.
Context
StackExchange Computer Science Q#16334, answer score: 7
Revisions (0)
No revisions yet.