DFA 中具有“1”的最小状态数作为右数第 5 个符号
DFA 接受“1”作为右数第 5 个符号的字符串所需的最少状态数是多少？字符串是通过字母表 {0,1} 定义的。
What is the minimum number of states needed in a DFA to accept the strings having '1' as 5th symbol from right? Strings are defined over the alphabet {0,1}.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Myhill-Nerode 定理是解决此类问题的有用工具。
这个想法是使用“区分扩展”的思想来构建一组字符串的等价类。考虑两个字符串 x 和 y。如果存在字符串z
这样，xz 和 yz 恰好之一在该语言中，那么 z 是一个可区分的扩展，
x 和 y 必须属于不同的等价类。每个等价类映射到最小 DFA 中的不同状态。
对于您所描述的语言，令 x 和 y 为任意一对不同的 5 个字符的字符串
超过{0,1}。如果它们在位置 n 处不同（从右数，从 1 开始），则任何长度为 5-n 的字符串 z 将是一个有区别的扩展：如果 x 在位置 n 处有 0，
并且 y 在位置 n 处有一个 1，则 xz 被拒绝，yz 被接受。得出 25 = 32
等价类。
如果 s 是长度 k < 的字符串5个字符，属于同一个等价类
为 0(5-k)s（即向左侧添加 0 填充，直到达到 5 个字符长）。
如果s是长度k>的字符串5 个字符，其等价类由最后 5 个字符决定。
因此，所有超过 {0,1} 的字符串都属于上述 32 个等价类之一，并且根据 Myhill-Nerode 定理，该语言的最小 DFA 有 32 个状态。
The Myhill-Nerode theorem is a useful tool for solving these sorts of problems.
The idea is to build up a set of equivalence classes of strings, using the idea of "distinguishing extensions". Consider two strings x and y. If there exists a string z
such that exactly one of xz and yz is in the language, then z is a distinguishing extension,
and x and y must belong to different equivalence classes. Each equivalence class maps to a different state in the minimal DFA.
For the language you've described, let x and y be any pair of different 5-character strings
over {0,1}. If they differ at position n (counting from the right, starting at 1), then any string z with length 5-n will be a distinguishing extension: if x has a 0 at position n,
and y has a 1 at position n, then xz is rejected and yz is accepted. This gives 25 = 32
equivalence classes.
If s is a string with length k < 5 characters, it belongs to the same equivalence class
as 0(5-k)s (i.e. add 0-padding to the left until it's 5 characters long).
If s is a string with length k > 5 characters, its equivalence class is determined by its final 5 characters.
Therefore, all strings over {0,1} fall into one of the 32 equivalence classes described above, and by the Myhill-Nerode theorem, the minimal DFA for this language has 32 states.
状态数将为 2^n，其中 n 是从右数第 n 个符号
所以 2^5=32 将是没有状态
No of state will be 2^n where n is nth symbol from right
So 2^5=32 will be no of states