0

我必须说明以下是否是常规集合。这些是我的答案，我想知道我是否正确并获得关于我的推理的额外输入。另外，我想在不使用抽水引理的情况下直观地使这些合理化，我被告知对于以下任何一个都不太难。

我只需要正式在底部显示问题。

   a. {(a^n)(b^m) | n!=m} 
   b. {xcx | x is in {a,b}*}
   c. {xcy | x,y is in {a,b}*}
   d. {(a^n)(b^n+481) | n >= 0}
   e. {(a^n)(b^m) | n>=m and m<= 481}
   f. {(a^n)(b^m) | n>=m and m>= 481}
   h. {(a^n)(b^n)(c^n) | n>=0}


a. Not regular. This would imply that {(a^n)(b^n) | n>=0} is regular, which isn't true either by the closure properties for regular sets.
b. For both b and c, I don't think I am conceptualizing it correctly. Since x can be any arbitrary string of a's or b's, I would say that both parts b and c are not regular. But I don't think that this is correct.
c. See above.
d. Not regular. From the same reasoning from a. Adding a constant really means nothing since n is unbounded positively. 
e. Unsure.
f. Unsure.
h. Not regular from the same reasoning as a.

最后我必须正式证明不存在 {(a^n)(b^n) | 的无限子集。n>=0} 使得子集是规则的。

这可以在没有抽水引理的情况下以简单的方式完成吗？由于我对常规套路没有很好的掌握，我还没有尝试过。

4

1 回答 1

1

这里有一些评论：

  • 对于（a），我相信你是对的，但你需要小心你如何证明为什么如果该语言是常规的，那么 { a n b n | N } 中的 n 是正则的。确保您了解要使用的闭包属性。

  • 对于 (b)，作为提示，使用同态。可以删掉c吗？

  • 对于 (c)，考虑一下这种语言的含义。是aabaabc语言吗？是caab语言吗？你能找到一种更简洁的方式来描述它，比如用正则表达式吗？

  • 对于 (d)，您可以通过在连接和联合下使用闭包来证明它不是规则的。你怎么看？

  • 对于 (e)，尝试将语言写为 { a n | n ≥ 0 } ∪ { 一个n b | n ≥ 1 } ∪ { 一n b 2 } ∪ ... { 一n b 471 | n≥471}。这有帮助吗？

  • 对于 (f)，作为提示，它不是规则的。鉴于（e）的直觉，你明白为什么吗？

  • 对于 (h)，使用与 (b) 中相同的技术。

最后，对于您的最后一个问题，您确实可以在这里使用抽水引理。在抽水引理的正常证明中，你会选择字符串 a p b p，其中 p 是抽水长度。您可以使用类似的技巧，但不能保证 a p b p在该语言中。但是，你能证明 a p+k b p+k必须在某些 k ≥ 0 的语言中吗？

希望这可以帮助！

于 2013-10-17T23:38:28.303 回答