我想知道两种语言（一种常规语言和另一种非常规语言）之间的连接是否总是不规则的，或者输出可能是常规语言。谢谢。
问问题
6672 次
3 回答
3
不，因为我们可以找到一个反例来证明它有时会发生：
L1 不规则：(a^2)^n with n>=0
L2 规则：a*
连接产生语言 L3= aa* ，这显然是正常的。
于 2016-11-21T13:53:40.073 回答
1
a^(2^n) n>=0 是非正则的，除非将它与正则的 a* 连接，从而产生正则语言。它变成了 L = {a^(2^n)a*, n>=0} ，它基本上取消了 L={aa*} ，这是常规的。
Patrick87, (a^2)^n n>1 有正则表达式 (aaaa)(aa)*
于 2019-02-16T05:42:50.093 回答
0
Remember that the empty language ∅ and the singleton language of the empty string {ε} are both regular. The concatenation of any nonregular language and the empty language is the empty language (regular), and the concatenation of any nonregular language and {ε} is the original language (nonregular). Therefore, the answer depends on the choice of languages.
(@Hyruma92 gives another example of where the concatenation gives a regular language; I added this answer because I think it more directly and simply gets you there. The intuition here is that the empty language is the zero element for language concatenation and {ε} is the identity element, which motivates why you might want to try them out.)
于 2019-06-11T02:17:12.127 回答