构造正规式的DFA 1(0|1)*101

正则表达式（regular expression）是记录文本规则的一种语言，可以用于搜索、匹配、替换文本。而DFA（deterministic finite automaton，确定性有限自动机）是一种计算模型，可用于判断某个字符串是否符合特定的语法规则。本文将从正则表达式和DFA的角度，详细分析如何构造一个满足1(0|1)*101规则的DFA。

一、正则表达式的构造

正则表达式是用于匹配文本的字符串模式。对于1(0|1)*101，我们可以先将其分解为三部分：1、(0|1)*、101。其中，*表示重复0次或多次，|表示或者。因此，该正规式可以描述为：以1开头，以101结尾，中间可包含任意个0或1。

二、构造状态图

DFA是一个有限状态机，它由一组状态、输入符号集、转移函数、起始状态和终止状态组成。对于1(0|1)*101，我们可以将其转化为状态图：


图中，用圆圈表示状态，每个状态都有一个标记，例如起始状态用一个小圆圈加上S的标记，以此类推。有向边表示状态之间的转移关系，箭头上标示转移的字符。

三、给状态编号

将状态图转化为DFA的关键是为每个状态都分配一个编号。对于1(0|1)*101的DFA来说，我们可以给每个状态都分配一个数字和名称：

0（S）：起始状态

1：接受101的状态

2：可接受0或1的状态

3：接受1的状态

4：接受10的状态

5：接受1010的状态

6：接受101的状态

7：拒绝的状态

四、为状态建立转移函数

DFA有一个主要的特征，那就是对于确定的输入（字母），转移函数将产生唯一的输出（状态）。对于1(0|1)*101规则的DFA，转移函数可以描述为：

| | 0 | 1 |

| --- | ----- | ----- |

| 0 | 7 | 2 |

| 1 | 7 | 7 |

| 2 | 4 | 3 |

| 3 | 7 | 1 |

| 4 | 5 | 3 |

| 5 | 6 | 3 |

| 6 | 7 | 7 |

| 7 | 7 | 7 |

根据转移函数，我们可以得到从任何状态开始，只要按照输入符号的规则进行输入，DFA都会不断地转移到下一个状态。如果最终转移到了可以接受的状态，那么意味着输入的串符合规则。

五、画出完整的DFA

通过前面的步骤，我们已经构造出了1(0|1)*101规则的DFA。现在，我们将其完整地画出来就是：


从起始状态0开始，我们可以看出，DFA会不断转移状态，直到我们达到某个接受状态。