从简单语句中绘制DFA（或NFA）的步骤是什么？

Question

我收到了一个简单的陈述：构建一个在字母表{0,1}上接受所有以101结尾的字符串的DFA？

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

注意：这只是对我来说一个小课程，所以我从未学习过像正则表达式之类的东西，也没有学习过任何用于构建DFA的算法。

- Solace

---

不要使用正则表达式。只需考虑有限状态机可能处于哪些状态。 - John Dvorak

你知道如何构建简单的确定有限状态自动机吗？比如，一个只接受'1'或'01'的DFA？ - Mdev

对于输入信号 '1'，状态转移将从初始状态开始并结束于自身；而对于输入信号 '0'，状态转移将从初始状态开始并结束于一个“死亡（die）状态”。因此，初始状态也将是接受状态。 - Solace

对于“01”，0和1的转换都将从初始状态开始，并以自身为结束状态，这使得初始状态也成为接受状态。 - Solace

@Human 这是我认为的。我不确定我是对还是错。 - Solace

现在尝试一下一个字符串的DFA，其中倒数第三个符号是1。 - Grijesh Chauhan

Answer 1

如果您想更详细地了解我是如何得出这个结果的，我很乐意解释，但现在我只是画了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.

- Mdev

---

你用什么工具画这个图形？ - Grijesh Chauhan

@GrijeshChauhan 我在Latex中使用了TeXLive的TikZ包。 :) 我在帖子末尾附上了TikZ DFA示例的链接。 - Mdev

谢谢，我会尝试一下。我使用dia，但这个看起来更清晰。我们可以制作彩色图片吗？ - Grijesh Chauhan

@grijeshchauhan 你是什么意思？是的，你可以。你可以在TikZ/LaTeX中做很多事情。 - Mdev

Answer 2

这里字符串应该以101结尾。因此我们需要为其绘制nfa，然后将其转换为DFA。 总状态是A、B、C、D。我会在这里上传一张图片，在图片中我已经绘制了NFA，然后绘制了它的转移表。接着我又绘制了将NFA转换为DFA的转移表。为了方便起见，我还绘制了DFA。

NFA中，当给当前状态输入特定输入时，机器会进入多个状态。它可以在给定的输入符号上零次、一次或多次移动。而在DFA中，当给当前状态输入特定输入时，机器只会进入一个状态。DFA在给定输入状态上只有一个移动。

将NFA转换为DFA的步骤如下： 步骤1：最初Q'=ϕ

步骤2：将NFA的q0添加到Q'中。然后找出从此起始状态的转移。

步骤3：在Q'中，查找每个输入符号的可能状态集。如果此状态集不在Q'中，则将其添加到Q'中。

步骤4：在DFA中，最终状态将是包含F（NFA最终状态）的所有状态。

在此处查看图片 点击这里

- Priyanka Reddi