Search code examples
algorithmmathsetregular-languagekleene-star

Kleene star semantics and set comparison

Say we have two languages L1 and L2, is the following condition below considered false?

(L1L2)* = L1*L2*

I'm assuming this because say:

Leftside of condition:

L1 = {a,b}
L2 = {c,d}

C = L1.L2
C = {ac,ad,bc,bd}

C* = {empty, 'acad','adbc','bdac',...}

Rightside of condition

L1 = {a,b}
L2 = {c,d}

L1* = {a,b,aa,ab,ba,bb,...}
L2* = {c,d,cc,cd,dc,dd,...}

C = L1*.L2*

C therefore can't have any element c within that has a combination such as "adbc" as can be demonstrated on the Leftside of the argument, therefore the original argument is false.

Is this approach valid?

Solution

  • I can't follow your proof, but if L1={a} and L2={b}, then (L1L2)* contains abab, and L1*L2* doesn't. So they're not equal.