regex - 从简单的陈述中得出 DFA（或 NFA）的步骤？

Question

我得到了一个简单的陈述：在alphabet {0, 1}接受的基础上构建一个 DFA all the strings that end in 101？

我的问题是，设计它的步骤是什么？或者设计一个 NFA，因为那时我知道将 NFA 转换为 DFA 的明确步骤，所以我会将 NFA 转换为 DFA。

注意：- 这对我来说只是一门小课程，所以我从来没有研究过像正则表达式这样的东西，或者任何可能用于构造 DFA 的算法。

Answer 1

如果您想进一步解释我是如何得出这个的，我很乐意解释，但现在我只是画了 DFA 并解释了每个状态。

对屏幕截图感到抱歉...我不知道如何将其直接转换为图像。

• 在状态 0 的输入 0 上，它循环回到自身。在 1 上，它准备自己结束，因为它可能是“101”。

• q1 在输入 1 上循环到自身，因为它仍在准备以“101”结束。在 q1 上输入“0”表示它正在准备输入“10”，所以它转到 q2。

• 在 q2 上输入“0”会中断整个循环并返回到 q0。输入“1”导致移动到接受状态 q3。

• q3 上的任何输入都会导致返回到输入对应的周期中的任何点。

• 也就是说，在“1”上，它返回到 q1，或在“101”中遇到第一个“1”的状态，准备结束。

• 在“0”上，它进入 q2，因为为了进入 q3，必须从 q2 输入“1”，所以无论如何，最后两个输入符号现在是“10”。

TikZ DFA 示例。