证明如果L1 L2⊆L2·L1

Question

让L1、L2成为这样的语言，使L2不再是空语言。

证明了如果L1中的空词epsilon，则L2是L2·L1的一个子集。

假设出现了L2⊈L2·L1的矛盾。因此，语言L1中包含的词不是空词，否则我们可以把ϵ和L_2中的每个单词连在一起，所以ϵ∉L1是一个矛盾。

这是个很好的证据吗？

谢谢!

Answer 1

看上去很好。再吃一杯：

(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)意思是“如果从级联中实际产生新的元素”，可以通过提供至少一种这种情况的例子加以证明：

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

值得注意的是，当L1拥有比ɛ更多的元素时，您可以获得相等。

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

例如：

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