是否可以证明L是正则语言？
设 L = {a^f(m) | m >= 1 } 其中 f: Z^+ -> Z^+ 是单调递增的，并且符合 Z^+ 中所有元素 n 都有一个属于 m >Z^+ 使得 f(m+1) - f(m) >= n。
是否可以证明L是正则语言？
Let L = {a^f(m) | m >= 1 } where f: Z^+ -> Z^+ is monotone increasing and complies that for all element n in Z^+ there is an m belonging to Z^+ such that f(m+1) - f(m) >= n.
Is it possible to prove that L is a regular language?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
令 f(x) = 2^x。对于任何正 n，f(n+1) - f(n) >= n。
L = {a^f(m)} 不规则。考虑字符串 a^(2^x + 1)。 FA处理完这样的字符串后，导致接受状态的最小字符串是a^(2^x - 1)，长度为2^x - 1。因此，每个x值都需要一个单独的状态。由于x（正整数）的值有无穷多个，因此不存在识别L的FA；因此，L 不是常规语言。
Let f(x) = 2^x. For any positive n, f(n+1) - f(n) >= n.
L = {a^f(m)} is not regular. Consider the strings a^(2^x + 1). After an FA processes such a string, the smallest string which leads to an accepting state is a^(2^x - 1), having length 2^x - 1. Therefore, a separate state will be needed for every value of x. Since there are infinitely many values of x (positive integers), no FA exists to recognize L; ergo, L is not a regular language.