常规语言与 1*0* 相交得到 1n0n
我正在读一本关于自动机理论的书，书中给出了一个例子，即具有相同数量的 0 和 1 的语言与 1*0* 相交将得到 1n0n，其中 n > 1。 0
所以我的问题是，如何找到一些与 1*0* 相交时也会得到 1n0n 的常规语言。有没有办法思考一下？
更新： 感谢您的回答！我想我想要找到的是一些常规语言，所以像 1n0n 这样的语言是行不通的；） 是否可以？有什么想法吗？
I'm reading a book on automata theory, and the book gives an example that a language with equal number of 0s and 1s intersects with 1*0* would result 1n0n, where n > 0
So my question is, how can I find some regular languages that when intersected with 1*0*, would also results in 1n0n. Is there a way to think about that?
update:
Thanks for the answers! I guess what I'm trying to find is some regular languages, so the ones like 1n0n wouldn't work ;)
Is it possible? Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
注意：具有相等且无限数量的 0 和 1 的语言不是常规语言。
至于你的问题，我认为你不需要添加任何更多的限制一些后面跟着一些零来得到n个后面跟着n个零除了您给出的两个之外。有无数种简单构造的语言满足以下条件：
A1nB0nC其中 A、B 和 C 是可以匹配零宽度的任何表达式。N.B. The language with an equal and unbounded number of 0s and 1s is not a regular language.
As for your question, I don't think there are any more restrictions you can add to some ones followed by some zeros to get n ones followed by n zeros other than the two you have given.There are an infinite number of trivially-constructed languages that satisfy the conditions:
A1nB0nCwhere A, B and C are any expressions that can match zero width.只需将问题想象为：“哪些语言与
1n0m相交时，给出语言1n0n？”基本上，任何添加 n=m 约束的东西。一个例子是
anbn，其中 a!=b。另一种是
L = { 1n0n1m0m | n!=m，n>=0，m>=0}。另外，正如 OrangeDog 指出的那样，
1n0n不是正则的，并且由于正则语言在交集下是封闭的，因此任何与1*0*交集的语言都给出1n0n不规则。Just think of the question as: "What languages, when intersected with
1n0m, give the language1n0n?" Basically, anything that adds the constraint that n=m.One example is
anbn, where a!=b.Another one is
L = { 1n0n1m0m | n!=m, n >= 0, m >= 0 }.Also, as OrangeDog pointed out,
1n0nis not regular, and since regular languages are closed under intersection, it follows that any language whose intersection with1*0*gives1n0nis not regular.