从正则表达式到NFA

正则表达式

定义 : 正则表达式可以描述所有通过对某个字母表上的符号应用连接闭包运算而得到的语言;可以用正则表达式定义的语言叫做正则集合

性质 : 如果两个正则表达式 r 和 s 表示同样的语言,则称 r 和 s等价

遵循一些代数性质

定律 描述
\( r | s = s | r \) | 是可以交换
\( r|(s|t) = (r|s)|t \) | 是可结合的
\( r(st) = (rs)t \) 连接是可结合的
\( r(s|t)=rs|rt \);\( (s|t)r=sr|tr \) 连接对|是可分配的
\( \epsilon r=r\epsilon =r \) \(\epsilon\)是连接的单位元
\( r^{*} = (r|\epsilon)^{*} \) 闭包中一定包含\( \epsilon \)
\( r^{**} = r^{*} \) * 具有幂等性

NFA

有穷自动机是识别器(recognizer),它能对每一个可能的输入串简单地回答“是”或者“否”

在上一篇也讲过自动机其实是5元组,这里不重复说了

Thompson算法

(以下部分均来源于龙书第四版)

算法转化分为两步,一个是正则基本表达式,第二个是基本表达式的运算

基本规则 :

对于 \( \epsilon \) 表达式 ,构造如下的NFA

对于只有字符\( a \)表达式,构造如下的NFA

运算封闭:

并运算

设正则文法 L 和 G,如下

\( L(x) = \{ x^{1} \} \)

\( G(y) = \{ y^{1} \} \)

并运算后的的NFA表达式 记为 \( M = (L \cup G) \),则有\( M(z) = \{z | z \in L 或 z \in G\} \)

连接运算

沿用上面的文法,设\( M = (LG) \),则有\( \{z = xy | x \in L 且 y \in G \} \),得到如下图

闭包运算

沿用上面记号文法\( M=\{z^{n} | z \in L 且 n \in N^{0}\} \)

下载visio文件