Thompson构造法

定义

基本思想：按结构归纳

在给定字母表$\Sigma$下，其正则表达式可由且仅由以下规则定义：

1. $ϵ$是作者表达式
2. $\forall a\in \Sigma$, $a$是正则表达式
3. 如果$s$是正则表达式，那么$(s)$是正则表达式
4. 如果$s$与$t$是正则表达式，那么$s|t$，$st$，$s^{\ast }$也是正则表达式

例子

$ϵ$是一个正则表达式

$\forall a\in \Sigma$, $a$是正则表达式

如果$s$是正则表达式，那么$(s)$是正则表达式

仅加一个括号，当中的语言不变

如果$s$与$t$是正则表达式，那么$s|t$是正则表达式

如何表达或者？

问题：

Question

如果$N(s),N(t)$的开始状态和接受状态唯一？

Answer 归纳假设，开始状态和接受状态均唯一

在构造的过程中保证这一点，在所有的构造过程中，始终保证这一点。 根据

如果$s$与$t$是正则表达式，那么$st$也是正则表达式

将s的终止状态连上t的初始状态

同样可以在构造过程中保证状态的唯一性

如果$s$与$t$是正则表达式，那么$s^{\ast }$也是正则表达式

添加4挑$ϵ$转移表达*，即可以表示0次或多次

Thompson构造法分析

性质

1. $N(r)$的开始状态和接受状态唯一
2. 开始状态没有入边，结束状态没有出边
3. $N(r)$的状态数$|S|\le 2\times |r|$，$|r|$表示$r$中运算符和运算分量的总和
4. 每个状态最多两个$ϵ-$入边，和两个$ϵ-$出边
5. $\forall a\in \Sigma$，每个状态最多有一个$a-$入边和一个$a-$出边

复杂度分析

$N(r)$的状态数$|S|\le 2\times |r|$，$|r|$表示$r$中运算符和运算分量的总和

复杂度是线性关系

例子

Question

r = (a|b)*abb