DFA的例子

示例1:

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

解决方案:

FA将有一个开始状态q0，从这个状态开始，只有输入1的边会进入下一个状态。

在状态q1，如果读取1，我们将处于状态q1，但如果在状态q1读取0，我们将到达状态q2，也就是最终状态。在q2状态下，如果读取0或1，我们将分别进入q2或q1状态。注意，如果输入以0结束，则它将处于最终状态。

示例2:

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

解决方案:

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

示例3:

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

解决方案:

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

这里q0是开始态，也是最终态。请仔细注意，保持了0和1的对称性。我们可以将每个状态的含义关联为:

Q0:偶数个0和偶数个1的状态。
Q1:奇数个0和偶数个1的状态。
Q2:奇数个0和奇数个1的状态。
Q3:偶数个0和奇数个1的状态。

示例4:

设计∑={0,1}的FA接受包含三个连续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:

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

解决方案:

DFA可以用转换图表示为: