L={ a^n b^n c^m d^m :n >= 1，m >= 1}U{ a^n b^m c^m d^n :n >= 1，m >= 1} isRegular？

Question

有很多例子可以用来证明引理，但是我没有弄明白这一点，有人能帮上忙吗？

L= { a^n b^n c^m d^m :n >= 1，m >= 1}U{ a^n b^m c^m d^n :n >= 1，m >= 1}

Answer 1

以常规语言R = a*b*cd为例。两种正则语言的交集必须是正则语言。L和R的交集是a^n b^n cd。然而，使用泵浦引理或Myhill-Nerode定理很容易证明这不是正则的。这是一个矛盾，所以L不能是规则的。