context-free-grammar - L = { a^nb^nc^md^m : n >= 1, m >= 1 } U { a^nb^mc^md^n : n >= 1, m >= 1 } 是正则吗？

Question

有很多关于pumpinglemma证明的例子，但我没有弄清楚这一点，有人可以帮忙吗？

L= { a^nb^nc^md^m : n >= 1, m >= 1 } U { a^nb^mc^md^n : n >= 1, m >= 1 }

标签： context-free-grammarregular-languageautomatacontext-free-languagepumping-lemma

Answer 1

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