记录
正则表达式 ( Regular Expression，RE )
简介
- 是一种用来描述正则语言的更紧凑的表示方法。
- 正则表达式可以由较小的正则表达式按照特定规则递归地构建。
- 每个正则表达式 r 定义(表示)一个语言，记为 L(r) 。
定义
- ε是一个RE，L(ε) = {ε}
- 如果 a∈∑，则a是一个RE，L(a) = {a}
- 假设 r 和 s 都是RE，表示的语言分别是 L(r) 和 L(s) ，则
- r|s 是一个RE，L( r|s ) = L(r)∪L(s)
- rs 是一个RE，L( rs ) = L(r) L(s)
- r* 是一个RE，L( r* )= (L(r))*
- (r) 是一个RE，L( (r) ) = L(r)
举例
C语言无符号整数的RE
- 十进制整数的RE - (1|…|9)(0|…|9)*|0
- 八进制整数的RE - 0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*
- 十六进制整数的RE - 0x(0|1|…|9|a|…| f |A|…|F)(0|…|9|a|…| f |A|…|F )*
代数定律
| 定律 | 描述 |
|---|---|
| r｜s = s｜r | ｜是可以交换的 |
| r｜( s｜t )=( r｜s )｜t | ｜是可结合的 |
| r(s t)=( r s)t | 连接是可结合的 |
| r ( s｜t )= r s｜r t ; ( s｜t ) r = sr｜t r | 连接对｜是可分配的 |
| εr = rε = r | ε 是连接的单位元 |
| r* = ( r｜ε )* | 闭包中一定包含 ε |
| r* * = r* | * 具有幂等性 |
单词的识别
有穷自动机 ( Finite Automata，FA )
- 具有一系列离散的输入输出信息和有穷数目的内部状态。
- 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。
- 每当系统处理了当前的输入后，系统的内部状态也将发生改变。
模型
- 输入带(input tape)：用来存放输入符号串。
- 读头(head )：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动。
- 有穷控制器( finite control )：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一状态。
表示：转换图 ( Transition Graph )
- 结点：FA的状态
- 初始状态（开始状态）：只有一个，由start箭头指向。
- 终止状态（接收状态）：可以有多个，用双圈表示。
- 带标记的有向边：如果对于输入 a ，存在一个从状态 p 到状态 q 的转换，就在 p 、 q 之间画一条有向边，并标记上 a 。
接收的语言
- 给定输入串 x ，如果存在一个对应于串 x 的从初始状态到某个终止状态的转换序列，则称串 x 被该FA接收。
- 由一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为 L( M )。
L(M) = 所有以abb结尾的字母表{a, b}上的串的集合
最长子串匹配原则
当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配。
有穷自动机的分类
- 确定的FA (Deterministic finite automata, DFA)
- 非确定的FA (Nondeterministic finite automata, NFA)
DFA
对任意的字符，最多有一个状态可以转移。
M = ( S，Σ ，δ，s0，F )
- S：有穷状态集。
- Σ：输入字母表，即输入符号集合。假设 ε 不是 Σ 中的元素。
- δ：将S×Σ映射到S的转换函数。∀s∈S, a∈Σ, δ(s,a) 表示从状态s出发，沿着标记为a的边所能到达的状态。
- s0：开始状态 (或初始状态)，s0∈ S。
- F：接收状态（或终止状态）集合，F⊆ S。
r = (a|b)*abb
NFA
对任意的字符，有多于一个状态可以转移。
M = ( S，Σ ，δ，s0，F )
- S：有穷状态集。
- Σ：输入字母表，即输入字母表。假设 ε 不是 Σ 中的元素。
- δ：将S×Σ映射到2^S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合。
- s0：开始状态 (或初始状态)，s0∈ S。
- F：接收状态（或终止状态）集合，F⊆ S。
r = (a|b)*abb
等价性
对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机D
对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N
主要区别
- 对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA就有可能得到一个状态集。因此NFA引擎必须记录所有的可能路径。
- DFA比较快，但不提供Backtrack（回溯）功能，NFA比较慢，但提供了Backtrack功能。
DFA的算法实现
由于DFA对于特定输入，状态是确定的，因此实现起来很方便。
- 输入：以文件结束符eof结尾的字符串x。DFA D的开始状态s0，接收状态集F，转换函数move。
- 输出：如果D接收x，则回答“yes”，否则回答“no”。
- 方法：将下述算法应用于输入串x12345678910s = s0;c = next_char();while (c != eof) {s = move(s, c);c = next_char();}if (s is in F)return "yes";elsereturn "no";
RE转换成NFA
ε
字母表Σ中符号a
r = r1r2
r = r1|r2
r = (r1)*
r=(a|b)*abb 对应的NFA
