是一种语言 L = {s ∈ (0 + 1)* | (0 + 1)* | d(s) mod 5 =2 和 d(s) mod 7 !=4 } 正则？
当我读一本书时，我有这样的疑问。
它提到
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod5 =0} 是正则 其中 n0(s) = s 中 0 的数量，n1(s) = s 中 1 的数量
进一步提到
L = {s ∈ (0 + 1)* | d(s) mod 5 =2 和 d(s) mod 7 !=4 } 不是常规的（甚至不是上下文无关的，但它是递归的） 其中 d(s) = s 的十进制值（例如 d(101) = 5）
为什么会这样？是因为 DFA 没有内存来存储（记住） s 的十进制值吗？但既然如此，为什么第一语言就被赋予了常规语言呢？
While reading from a book I had this doubt.
It mentions that
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod5 =0} is regular
Where n0(s) = number of 0’s in s and n1(s) = number of 1’s in s
Further it mentions that
L = {s ∈ (0 + 1)* | d(s) mod 5 =2 and d(s) mod 7 !=4 } is not regular (not even context-free but it is recursive)
Where d(s) = decmial value of s (e.g. d(101) = 5)
Why is it so? Is it because a DFA doesn’t have memory to store (remember) the decimal value of s? But in that case how come the first language is given to be regular?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你的教科书要么有错误，要么你误读了它：你命名的第二语言是常规语言。
DFA 可以计算二进制数（或任何基数）模 m 的值（对于任何 m）。只需将 m 个状态编号为 0 到 m-1；当读取零时，从当前状态s转到(s*2) mod m；读取 1 时，转到 (s*2+1) mod m。要了解其工作原理，只需查看二进制文件的工作原理，即 (a + b) mod m = (a + b) mod m = (a + b) mod m >a mod m + b mod m) mod m （乘法类似）。
要接受等于 k mod m 的数字，请将 k 设置为接受状态；要接受与 k mod m 不同的数字，请让所有其他状态接受。
这意味着 {s ∈ {0,1}* | d(s) mod 5 = 2} 且 {s ∈ {0,1}* | d(s) mod 7 != 4 } 都是常规语言。语言L是它们的交集，正则语言在交集下是封闭的，所以L是正则的。
语言 {s ∈ {0,1}* | d(s) mod 5 = 2} 被正则表达式接受'(((0*10(10*10)*10*11|0*11)((00|1)(10*10)*10*11|01)*(00|1)(10* 10)*0|0*10(10*10)*0)(0((00|1)(10*10)*10*11|01)*(00|1)(10*10)*0 |1)*0((00|1)(10*10)*10*11|01)*(00|1)(10*10)*|(0*10(10*10)*10*1 1|0*11)((00|1)(10*10)*10*11|01)*(00|1)(10*10)*|0*10(10*10)*)$' （我在这里使用了 Python 表示法，但要获得您的表示法，只需将 | 替换为 + 并删除 $）。
There is either a mistake in your textbook or you are misreading it: the second language you name is regular.
A DFA can compute the value of a binary number (or any base number) modulo m (for any m). Simply have m states numbered 0 to m-1; when reading a zero, go from the current state s to (s*2) mod m; when reading a one, go to (s*2+1) mod m. To see that this works, one needs only to look at how binary works, and that (a + b) mod m = (a mod m + b mod m) mod m (and similarly for multiplication).
To accept numbers which are equal to k mod m, make k an accepting state; to accept numbers different from k mod m, make all other states accepting.
This means {s ∈ {0,1}* | d(s) mod 5 = 2} and {s ∈ {0,1}* | d(s) mod 7 != 4 } are both regular languages. The language L is their intersection, and the regular languages are closed under intersection, so L is regular.
The language {s ∈ {0,1}* | d(s) mod 5 = 2} is accepted by the regular expression '(((0*10(10*10)*10*11|0*11)((00|1)(10*10)*10*11|01)*(00|1)(10*10)*0|0*10(10*10)*0)(0((00|1)(10*10)*10*11|01)*(00|1)(10*10)*0|1)*0((00|1)(10*10)*10*11|01)*(00|1)(10*10)*|(0*10(10*10)*10*11|0*11)((00|1)(10*10)*10*11|01)*(00|1)(10*10)*|0*10(10*10)*)$' (I have used Python notation here, but to obtain your notation simply replace | by + and remove the $).