discrete-mathematics - 如何构造一个识别以两个 D 开头的位串集的 dfa？

Question

我需要这个解决方案的帮助，因为我刚刚开始研究有限状态自动化并且无法帮助自己解决这个问题。

这个问题是否意味着我必须提供输入 1101 1101 如果是这样，如果位字符串不是以两个 D 开头，如何显示要进入的另一个状态

标签： discrete-mathematicsdfafinite-state-automaton

Answer 1

假设 D 表示十进制数 13 的十六进制表示，那么是的，相同数字的二进制表示是 1101 并且以两个 D 开头的字符串集（意思是二进制字符串的十六进制表示以两个 D 开头）将是以 11011101 开头的字符串集。要使用 DFA 接受此类字符串，您需要十个状态：

• 初始状态
• 字符串中每个符号的一个状态
• 死状态

转换将从初始状态转到与字符串符号对应的每个状态，按顺序，在这些位置的符号上。任何不合适的输入都会导致最后一个死状态，该状态会循环到自身。唯一接受的状态是与字符串的最后一个符号对应的状态，并且它也会循环到自身（因为通过附加到此基数形成的任何字符串也是您语言中的字符串）