regex - 从简单语句中绘制 DFA(或 NFA)的步骤？

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

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

注意:- 这对我来说只是一个次要类(class)，所以我从来没有研究过像正则表达式这样的东西，或者任何可能用于构建 DFA 的算法。

最佳答案

如果你想要更多关于我如何得出这个的解释，我很乐意解释，但现在我只是画了 DFA 并解释了每个状态。

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

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

q1 在输入 1 上循环到自己，因为它仍在准备结束
'101'。在 q1 上输入 '0' 意味着它正在准备输入 '10'，所以它转到 q2。

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

q3 上的任何输入都会导致返回到循环中的任何点
输入对应。

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

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

TikZ DFA examples.

关于regex - 从简单语句中绘制 DFA(或 NFA)的步骤？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23273352/