构造下列正规式的dfa:1(0|1)*101

随着计算机技术的不断发展，正规式成为了计算机科学中一个必不可少的概念。正规式（regular expression）是指用来描述一类字符串集合的一种方式。DFA是一种可接受或拒绝一种特定语言的有限状态自动机，它是理论计算机科学中的重要概念。本文旨在通过对正规式1(0|1)*101的DFA的构造来分析正规式和DFA的关系。

一、正规式1(0|1)*101的解释

正规式1(0|1)*101表示以“1”开头，“01”或“11”可以出现任意次数，“101”结尾的字符串。可以理解为这个正规式描述了一个二进制数字串，它的首位是1，中间可以有0或1（可以是0,1的排列组合，可以出现任意次数），最后三位是101。

二、DFA构造的基本思路

首先考虑1的作用，它表示以1开头，所以DFA的起始状态为S0，接下来进入状态S1。然后考虑两个1中间可以随意插入0和1，因此我们需要两个状态S1和S2，它们都可以接受0或1，并且可以自我循环，表示0或1可以出现0次或多次。接着考虑“101”的作用，它表示结束，因此我们需要一个接受状态S3。

三、DFA构造的详细过程

1.构造NFA

首先将正规式转化成NFA。首先，我们将正规式1(0|1)*101分解成三部分：1，(0|1)*，101。因为1和101都是确定的值，我们可以将它们看作单个状态。而对于(0|1)*，我们需要构造一个可以接受0或1的状态S1，然后将它指向自身，并将退出该状态的转移边指向101。最后将三个部分串联在一起，得到如下NFA表示：

```

S0 -1-> S1 -0,1-> S2 -1-> S3

```

2.将NFA转化为DFA

将NFA转化为DFA，就是要将NFA中的状态表示成DFA中状态的子集。为了便于说明，我们首先对NFA进行子集构造：

```

S0 {S0}

S1 {S1, S2}

S2 {S3}

S3 {}

```

构建完子集，我们再来看NFA，可以发现，S1状态可以通过0或1转移到自身或S2，因此我们需要构建一个新状态{S1， S2}。然后，我们还需要通过0或1进行状态转移，考虑到状态S1和S2相同的性质，我们可以将标记为*的部分（S1或S2）一并转移，得到DFA如下：

```

0 1

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

->S0| S0 S1

S1,|S1,S2(*) S2(*)

<-S2| S3 S3

```

四、DFA的优化

我们可以对DFA进行优化，去掉一些无用的状态和转移。首先我们可以去掉S3状态，因为它没有从它本身出发的转移路径，也就是说接受的字符串已经完整了。去除S3后，相应地，我们需要在S0和S1上加上由0或1指向自身的路径，表示0或1可以出现0次或多次。最终的DFA如下：

```

0 1

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

->S0|S0,S1(*) S1

<-S1| S0 S2

```