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”之类的组合，这可以在参数的左侧证明，因此原始参数是错误的。

这种方法有效吗？

score 2 · Accepted Answer

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.

1 回答 1