有限状态自动机与正规表达式

有穷自动机表示的语言是正规语言，二者等价。

从正规表达式构造 $ϵ$ - NFA

Thompson 构造法

从 DFA 构造正规表达式

路径迭代法

• 将状态集用 $\left\{1,2,\dots ,n\right\}$ 表达，初态为 1
• 对所有 $1\le i,j\le n,0\le k\le n$ 迭代计算 $R_{ij}^{(k)}$，表示一个正规表达式，从 $i$ 到 $j$ 有一条标记为 $w$ 的路径，且路径上所有点除 $i$ 和 $j$ 外不大于 $k$
  • $k=0$ 时
    • 若 $i\ne j$，若不存在从 $i$ 到 $j$ 的弧，$R_{ij}^{(0)}=\varnothing$，否则 $R_{ij}^{(0)}=a_1+a_2+\cdots +a_m$
    • 若 $i=j$，若不存在自环，$R_{ij}^{(0)}=ϵ$，否则 $R_{ij}^{(0)}=ϵ+a_1+a_2+\cdots +a_m$
  • $R_{ij}^{(k)}=R_{ij}^{(k-1)}+R_{ik}^{(k-1)}(R_{kk}^{(k-1)}{)}^{\ast }{R}_{kj}^{(k-1)}$
• 迭代计算得到 $R_{ij}^{(n)}$
• 将所有 $R_{1j}^{(n)}$ 相加（$j$ 为终态）

Example

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q1) {$q_1$};
		\node [state, accepting, right of = q1] (q2) {$q_2$};
		\draw (q1) edge[loop above, above] node{1} (q1)
			(q1) edge[above] node{0} (q2)
			(q2) edge[loop above, above] node{0,1} (q2);
	\end{tikzpicture}
\end{document}

状态消去法

思路：

• 扩展自动机的概念，允许转移弧是正规表达式
• 消去某一中间状态时，更新每一个前驱状态到每一个后继状态转移弧
• 对每一终态 $q$，消去除 $q$ 和 $q_0$ 外的所有状态
• 若 $q\ne q_0$，可得到以下自动机，对应的正规表达式可表示为 $(R+S{U}^{\ast }T{)}^{\ast }S{U}^{\ast }$

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, accepting, right of = q0] (q) {$q$};
		\draw (q0) edge[loop above, above] node{R} (q0)
			(q0) edge[above, bend left] node{S} (q)
			(q) edge[below, bend left] node{T} (q0)
			(q) edge[loop above, above] node{U} (q);
	\end{tikzpicture}
\end{document}

• 若 $q=q_0$ ，可得到以下自动机，对应的正规表达式可表示为 $R^{\ast }$

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial, accepting] (q0) {$q_0$};
		\draw (q0) edge[loop above, above] node{R} (q0);
	\end{tikzpicture}
\end{document}

• 最终的正规表达式为全部终态对应的正规表达式的并