正则表达式

正则表达式（Regular Expression，RE）是一种用来描述正则语言的更紧凑的表示方法

例如：r = a(a|b)*(ε|(.|_)(a|b)(a|b)*)

正则表达式可以由较小的正则表达式按照特定规则递归构造。每个正则表达式r定义（表示）一个语言，记为L(r)。这个语言也根据r的子表达式所表示的语言递归定义。

例子：

digit → 0|1|..|9

digits → digit digit*

可选小数部分：optionalFraction → .digits|ε

可选指数指数部分：optionalExponent → (E(+|-|ε)digits)|ε

number → digits optionalFraction optionalExponent
1
2
# 例子
2	2.15	2.15E+3		2.15E-3		2.15E3		2E-3

有穷自动机

有穷自动机的定义

是对一类处理系统建立的数学模型。这一类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：对过去输入信息处理的状态）。参考有限状态机。

FA的典型例子：电梯控制装置

输入：顾客乘电梯的需求（要达到的楼层号）
状态：电梯所处的层数和运动方向
电梯控制装置不需要记住先前全部的服务要求，只要记住电梯当前所处的状态以及还没满足的所有服务请求。

FA定义（接收）的语言

L(M) = 所有以abb结尾的字母表{a，b}上的串的集合

最长子串匹配原则

所以上面的例子中，输入串中匹配的应该是“<=”和“++”，而不是“<”和“=”或者两个“+”

有穷自动机的分类

确定的有穷自动机(DFA)

转换图和转换表是等价的，所以可以不用转换表来表示状态转移。

非确定的有穷状态机(NFA)

不确定的FA就是，一个状态，沿着标记为a的边出发，不止到达一个状态。例如上面的状态0，沿着a的标记边出发，可以到达状态0和状态1。如果某个状态从一个标记的边出发不能到达任何状态，就把空集放到表项中，例如上面的状态1通过a边，就不能到任何状态。

DFA和NFA的等价性

对于任意的NFA N，存在识别同一语言的DFA D
对于任意的DFA D，存在识别同一语言的NFA N

NFA看起来分析起来要更加直观简单，但是计算机实现DFA要更容易一点

带有“ε-边”的NFA

r = 0*1*2*

DFA的算法实现

前面说到DFA在计算机实现上要比NFA更加容易，下面是它的算法实现

s表示当前状态，如果最后s在接收状态集F中，则表示成功接收。否则到不确定状态了，就回答no。

从正则表达式到有穷自动机

前面说到DFA在计算机上要更容易实现，但是NFA要更加容易分析，所以我们通常先得到NFA，再得到DFA

根据RE(正则表达式)构造NFA

从NFA到DFA的转换方法

方法就是从初始状态开始，到第一个状态A，然后看所有的边，只有a可以进入非空下一状态，所以A通过a进入状态{A,B}，也就是DFA中的A,B状态；然后看状态A和状态B的所有边，首先是a，可以进入{A,B}和∅，它们的并集就是{A,B}，所以状态A,B可以通过a边进入自身，同理通过b可以进入{B,C}和∅的并集，所以状态A,B通过b边进入状态B,C；然后看状态B,C，方法和前面一样，最后得到通过b进入自身，通过c进入状态C,D；状态C,D是终止状态，只能通过c进入自身。

最多只能进入到自身的状态就是终止状态太。不能进入到自身的状态同时不需要任何条件进入下一状态的一般是起始状态，这列的start就是自动进入状态A的

如果类似于C,D状态这种状态，它包含在NFA中的终止状态D，那么在DFA中C,D状态就是终止状态

在看一个例子