regular-language - 证明正则语言

Question

我必须证明这个说法是错误的。如果 L1 = {ab| a∈L2, b∉L2} 是正则语言，则 L2 是正则语言。

（a 和 b 是字符串。）（假设 L1 和 L2 具有相同的字母。）

我的工作：
这个问题可以重写为：如果 L2 是规则的，那么 L1 是非常规的。（证明这是真的）

对立证明：如果 L2 是正则的，则 L1={ab| a∈L2, b∉L2} 是非常规的

我不确定在这条线之后该怎么做。这是正确的方法吗？有人可以给我一些关于如何做到这一点的提示吗？

Answer 1

令 A = "L1 = {ab| a∈L2, b∉L2} 是正则语言"。
令 B =“L2 是一种常规语言”。

问题是要证明 A → B 是假的。这等价于证明 A ∧ ¬B。用英文写着：

L1 = {ab| a∈L2, b∉L2} 是正则语言，但 L2 不是正则语言。

所以一种策略可能是找到一个非常规的 L2 导致 L1 是规则的。如果你能做到这一点，那么你就有了一个反例，所以你已经证明了原始陈述是错误的。