跳转至

自动机到正则表达式

  • DFA，NFA，\(\epsilon\)-NFA和正则表达式在表示语言的能力上是等价的

img

定理

若\(L=L(A)\)是某DFA \(A\)的语言，那么存在正则表达式R满足\(L=L(R)\)

证明：递归法

对A的状态进行编号，令1为开始状态，即\(A=(\{1,2,3,\dots,n\},\Sigma,\delta,1,F)\)

设正则表达式 \(R_{i,j}^{(k)}\) 表示从\(i\)到\(j\)但中间节点状态编号不超过\(k\)全部路径的字符串集(简称k-路径):

  • 归纳基础：\(k=0\), \(R_{i,j}^{(0)}\)为从\(i\)直接到\(j\)，没有经过任何中间节点的字符串集合
  • 情况一：\(i\neq j\)
    • 没有i到j的状态转移 \(R_{i,j}^{(0)}=\phi\)
    • 有一个i到j的转移 \(R_{i,j}^{(0)}=a\)
    • 有多个i到j的转移 \(R_{i,j}^{(0)}=a_1+\dots+a_t\)
  • 情况二:\(i=j\)
    • 状态i没有到自身的转移 \(R_{i,j}^{(0)}=\epsilon\)
    • 状态i有一个到自身的转移 \(R_{i,j}^{(0)}=a+\epsilon\)
    • 状态i有多个到自身的转移 \(R_{i,j}^{(0)}=a_1+\dots+a_t+\epsilon\)
  • \(R_{i,j}^{(k)}\)有两种情况
    • 不经过状态k
    • 经过状态k一次或多次

得到如下递归关系

\[R_{i,j}^{(k)}=R_{i,j}^{(k-1)}+R_{i,k}^{(k-1)}(R_{k,k}^{(k-1)})^*R_{k,j}^{(k-1)}\]

img

这个递归关系实际上可分为「“不经过k”的状态节点集合」与「经过了k节点的集合」
「经过了k节点的集合」当中“经过k节点”的状态又分为两种：经过1次/多次，可以由下图表示

img

如果1是开始结点，则和DFA等价的正则表达式就是

\[\bigcup_{j\in F}R_{1,j}^{(n)}\]

即从状态1（开始状态）到终结状态的所有路径的集合。

DFA to 正则表达式

例：把下图所示DFA转换成正则表达式。这个DFA接收至少含有一个0的串

img

状态消除法

img

  • DFA和从开始节点到结束节点所有路径对应的正则表达式集合等价；如果DFA能转化成只含有开始节点和终止节点的形式，则只需把开始节点到终止节点所有边上的正则表达式取出来即可
  • 利用空转移，增加新的开始和结束状态
  • DFA中的“路径”与正则表达式运算（连接，加，闭包）的关系

img

在删除状态节点时，要为被删除的状态S的每个“入”和“出”路径的组合, 补一条等价的新路径, 并用新的正则表达式表示

正则表达式 to 自动机

定理

每个正则表达式定义的语言，都可被有穷自动机识别

证明

  • 归纳基础
  • 对正则表达式∅，有ε−NFA
  • 对正则表达式ε，有ε−NFA
  • ∀a∈Σ，对正则表达式a，有ε−NFA

  • 归纳递推
    • r+s的ε−NFA
    • rs的ε−NFA:
    • r^∗的ε−NFA