DFA 示例

示例 1

设计一个FA，∑ = {0, 1}，接受以1开头，以0结尾的字符串。

解决方案

FA将有一个起始状态q0，只有输入为1的边会到达下一个状态。

在状态q1中，如果我们读取1，我们将保持在状态q1，但是如果我们在状态q1中读取0，我们将到达最终状态q2。在状态q2中，如果我们读取0或1，我们将分别进入q2状态或q1状态。请注意，如果输入以0结尾，它将处于最终状态。

示例 2

设计一个FA，∑ = {0, 1}，只接受输入101。

解决方案

在给定的解决方案中，我们可以看到只有输入101会被接受。因此，对于输入101，没有显示其他输入的其他路径。

示例 3

设计FA，∑ = {0, 1}，接受偶数个0和偶数个1。

解决方案

此FA将考虑输入0和输入1的四个不同阶段。这些阶段可以是

这里q0是一个起始状态，也是最终状态。请仔细注意，保持了0和1的对称性。我们可以将含义与每个状态相关联，如下所示

q0: 偶数个0和偶数个1的状态。
q1: 奇数个0和偶数个1的状态。
q2: 奇数个0和奇数个1的状态。
q3: 偶数个0和奇数个1的状态。

示例 4

设计FA，∑ = {0, 1}，接受具有三个连续0的所有字符串的集合。

解决方案

将为此特定语言生成的字符串是000、0001、1000、10001、....，其中0始终以3个一组的形式出现。转换图如下

请注意，维护三重零的序列以达到最终状态。

示例 5

设计一个DFA L(M) = {w | w ε {0, 1}*}，其中W是不包含连续1的字符串。

解决方案

当出现三个连续的1时，DFA将是

这里，两个连续的1或单个1是可以接受的，因此

状态q0、q1、q2是最终状态。DFA将生成不包含连续1的字符串，例如10、110、101等。

示例 6

设计一个FA，∑ = {0, 1}，接受后跟单个1的偶数个0的字符串。

解决方案

DFA可以通过转换图来显示，如下所示