任何dfa都不能识别空符号串吗

1.任何DFA都不能识别e(空)符号串

2.一个DFA,只能包含唯一的开始状态3.DFA识别的符号串集合,可以是有限的

4.一个DFA,所有的映射必须是单值...

否则太累了

--我们必须尽量优化程序才能达到题目的要求。显然n实在是太大了，所以我们不但不可能忍受O(n2)的复杂度，甚至连n前面的系数过大都会造成超时。为了尽量减小时间复杂度，我们只能依靠自动机的理论。

自动机理论

一个DFA（确定性有限自动机）是一个五元组<∑, U, s, T, φ>，其中∑是字符集U 是一个有限的状态集合, s 是 U 的一个元素表示初始状态, T 是 U的一个子集，表示终止状态and φ : U × ∑ → U 是转移函数。

开始时自动机在初始状态s，每步它读入一个字符c，然后根据state=φ(state,c)进行状态的转移。如果当字符串结束时它达到了终止状态，那么就说它接受了字符串。

NFA（非确定性自动机）与DFA的主要区别就是，NFA从一个状态按照一个字符转移到的状态可能有多个。因此NFA需要使用一个状态集合来表示当前可能处在的状态。

把自动机用图来表示的话，一般用结点表示状态，而结点之间有标有某个字符的有向边，表示可以从边的起点通过这个字符转移到边的终点。

此外NFA还可以包含标有ε的边，这种边表示不需要任何字符就可以直接进行状态的转移。

容易想到，如果我们建立了一个只接受符合正则表达式的自动机，就可以通过它来较快的判断哪些位置是可匹配的。

具体应用

比较常见的字符串匹配自动机大多都是DFA。但是由于有+，*，把正则表达式直接转变成DFA是非常困难的。因此我们只能先把它转化成NFA。

先看一下一般的转换规则：

如果正则表达式是一个字符，那么对应的NFA是：

p0-a->p1

如果正则表达式是A+B的形式，那么只要把它们的起始状态和终止状态合并就可以：

p0-a->p1

p0-b->p1

如果正则表达式是AB的形式，那么只要把A和B对应的自动机首尾相接：

p0-a->p1-b->p2

如果正则表达式是A*的形式，那么就需要按下面的图来进行处理：

p0-a->p0

p0->p1

通过上面的步骤可以得出：NFA的状态数不会超过正则表达式长度。

NFA中的状态转移

在NFA中进行状态转移比DFA要困难一些。我们可以定义两个函数，一个叫做epsilon-closure，用来计算一组NFA状态通过epsilon边能够到达的NFA状态集合。另外一个move用来在NFA上进行状态的转移。

设当前的状态集合是now，那么状态转移的过程就是：

new = {}

for every state s in now do

new = new ∪ {t | (s,t) = c}

new = epsilon_closure(new)

其中的(s,t)=c表示从s状态经过一个字符c可以转化到t状态。因为这个语句需要的集合总数也不会太多，所以可以通过预先计算出它们来加快速度。预处理后这个过程的复杂度是O(m2)，而系数是比较小的。

但是由于在NFA中，我们必须把状态的集合作为一个真正的状态，每次状态转移都是对这个集合的处理。这样转移一次的复杂度是O(m2)，这是不可忍受的（最大的数据需要大约2分钟才能出解）。

既然NFA速度过慢，我们自然想要把它转化为DFA。因为DFA中的状态转移是O(1)的。可是并没有一个多项式复杂度的方法可以把NFA转换成DFA。一般介绍的NFA转换到DFA的方法都是通过类似BFS的方法来把NFA中所有可能出现的状态集合对应成DFA的一个状态。

这种转换在本题中显然是不可行的，因为NFA的结点数最多是500，而转化成的DFA则可能有多达2500个状态，即使实际有许多状态不能达到，也是无论如何不可以忍受的。

看来把NFA转换成DFA是行不通的。但是我们还是从NFA转DFA的过程中受到了一些启发：NFA之所以速度慢，是因为我们在进行状态转移的时候可能进行许多重复 *** 作：比如从{1,2}沿一个字符1转移后是{2,3}，以后我们还可能遇到相同的情况，而这时我们还会用O(m2)的时间去进行状态转移。这是一种很严重的浪费。因此我们每进行一次状态转移，就把这个状态转移的情况放到hash表中，以后使用的时候就可以查找了。这相当于只把我们需要的一部分子集转移成DFA，虽然一般情况下并不能降低时间复杂度，但是在实际应用中确实很有效。（特别是对于没有*和括号的自动机，这样做可以保证线形的时间复杂度）

算法回顾和细节

我们重新来看一下算法的框架：

根据正则表达式建立NFA

now = start

while not eof do begin

read(c)

if 曾经进行过now,c的转移 then 利用以前的结果

else 进行状态转移并记录结果

if 终止状态 in now then 输出当前位置

end

建立NFA有各种方法，由于NFA并不会很大，所以我们可以使用递归的方法来实现。为了尽量减小系数，我们使用位压缩的方式来实现集合，并采用较为简化的hash函数（比如把一个集合位压缩后的一系列整数加起来取对220的余数），并在输入和输出的时候通过缓冲区来加快速度。这样就基本可以达到题目的时间要求。

但是注意到字符串可能有10M，而产生的NFA的状态集合最多也可能有10M个，而每个集合都需要100到200字节的存储空间，大大超出了允许的空间范围。因此我们需要对hash表的规模加以严格限制。如果规模过大就不得不放弃存储状态的想法，牺牲一定的时间来换取空间。

先化成带空转移的dfa，在去空符号。构造正规式1(0|1)*101相应的DFA。

(A|B)*表示A或者B出现若干次或者不出现。

(A*B*)* A出现若干次或者不出现，B出现若干次或者不出现，一起出现若干次或者不出现

(A*|B*)* A出现若干次或者不出现或者B出现若干次或者不出现，一起出现若干次或者不出现。

任何一个字符串都匹配这个字符串。

扩展资料：

正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”）） *** 作的一种逻辑公式。

就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。