证明正则语言

Question

我必须证明这句话是假的。如果L1 ={ab\ a∈L2，b∉L2}是一种正则语言，那么L2是一种正则语言。

(a和b是字符串。)(假设L1和L2有相同的字母。)

我的工作： 这个问题可以重写为:如果L2是正则的，那么L1是非正则的.(证明这是真的) 对比证明:如果L2是正则的，则L1={ab_a∈_2，b_∉_2}是非正则的。

我不知道这句话之后该怎么办。这是正确的方法吗？有人能给我一些怎么做的提示吗？

Answer 1

设A= "L1 ={ab\ a∈L2，b∉L2}是一种正则语言“。

设B= "L2是一种常规语言“。

问题是证明A→B是假的。这相当于证明英语中的A∧b：

L1 ={ab_a∈_2，b∉_2}是一种正规语言，但L2不是正规语言。

因此，一种策略可能是找到一个非正则的L2，从而导致L1是正则的。如果你能做到这一点，那么你就有了一个反例，所以你已经证明了最初的陈述是错误的。