setautomataformal-languagesset-theory

Prove that if ϵ ∈ L1 then L2 ⊆ L2 • L1

Let L1, L2 be languages such that L2 is not the empty language.

Prove that if the empty word epsilon in L1, then L2 is a subset of L2•L1.

Assume towards a contradiction that L2 ⊈ L2•L1. Thus, the language L1 contains words that are not the empty word, otherwise we could take ϵ and concatenate it to every word in L_2. So ϵ ∉ L1 which is a contradiction.

Is that a good proof?

Thanks!

Solution

  • It looks fine. Have another one:

    (1) ɛ•ω=ω•ɛ=ω for ∀ω∊L2;
(2) From (1) → ω∊L2•{ɛ} for ∀ω∊L2;
(3) From (2) and ɛ∊L1 → ω∊L2•L1 for ∀ω∊L2;
(4) From (3) and ω=ω for ∀ω∊L2 → L2=L2•L1 for L1={ɛ};
(5) If |L2⋂L2•L1|>0 then L2⊂L2•L1, where |X| is the number of elements in X;
(6) From (4) and (5) → L2⊆L2•L1

    (5) Means "if new elements are actually created from the concatenation", which can be proven by giving an example of at least one such case:

    L1={ɛ,a}
L2={b}
L2•L1={b,ba}
{b}⋂{b,ba}={ba}
|{ba}|=1

    Its worth noting that, you can get equality when L1 has more elements than ɛ.

    If |L2⋂L2•L1|=0 then L2=L2•L1

    For example:

    L1={ɛ,a}
L2=a+
L2•L1=L2=a+