我正在阅读一本关于自动机理论的书，书中给出了一个示例，即具有相同数量的 0 和 1 的语言与 1*0* 相交会导致 1n0n，其中 n > 0
所以我的问题是，我怎样才能找到一些与 1*0* 相交时也会产生 1n0n 的常规语言。有没有办法考虑这个？
更新：感谢您的回答！我想我想要找到的是一些常规语言，所以像 1n0n 这样的语言是行不通的；）有可能吗？有任何想法吗？
问问题
391 次
2 回答
1
注意 0 和 1 数量相等且无限制的语言不是常规语言。
至于你的问题，我认为除了你给定的两个之外，你可以添加一些限制，然后是一些零，以获得n 个一个，然后是 n 个零。
有无数种简单构造的语言可以满足以下条件：A1nB0nC其中 A、B 和 C 是可以匹配零宽度的任何表达式。
于 2011-02-08T21:44:49.647 回答
1
把这个问题想象成：“什么语言，当与 相交时1n0m，给出语言1n0n？” 基本上，任何增加 n=m 约束的东西。
一个例子是anbn，其中 a!=b。另一个是L = { 1n0n1m0m | n!=m, n >= 0, m >= 0 }.
此外，正如 OrangeDog 指出的那样，它1n0n不是正则的，并且由于正则语言在交集下是封闭的，因此任何与give 相交的语言都是不正则的。1*0*1n0n
于 2011-02-08T21:52:55.433 回答