algorithm - Kleene 星语义和集合比较

Question

假设我们有两种语言 L1 和 L2，下面的条件是否被认为是错误的？

(L1L2)* = L1*L2*

我假设这是因为说:

条件左侧:

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

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

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

条件右侧

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

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

C = L1*.L2*

因此 C 中不能有任何元素 c 具有诸如“adbc”之类的组合，这可以在参数的左侧证明，因此原始参数为假。

这种方法有效吗？

Answer 1

我无法遵循你的证明，但如果 L1={a} 和 L2={b}，则 (L1L2)* 包含 abab，而 L1*L2* 不包含。所以他们不相等。