0

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

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

4

1 回答 1

0

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

于 2018-08-16T19:30:27.077 回答