CODEWITHSUNDEEP
setautomataformal-languagesset-theory
user19756157
user19756157

Reputation: 63

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!

Upvotes: 0

Views: 380

Answers (1)

Nikolay Handzhiyski
Nikolay Handzhiyski

Reputation: 1579

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+

Upvotes: 1

Related Questions