1. 基础
集合A的n次幂(\(n≥0\))递归地定义为： \[
\begin{equation}
A^n=
\begin{cases}
\left\{\varepsilon\right\}& \text{ $ n=0 $ } \\
A^{n-1}A& \text{ $ n≥1 $ }
\end{cases}
\end{equation}
\] 
- 克林闭包：\(\Sigma^*=U_{i=0}^{∞} \Sigma^i\)
- 正闭包：\(\Sigma^+=U_{i=1}^{∞} \Sigma^i\)
- \(\Sigma^*=\Sigma^+ \or \left\{\varepsilon\right\}\)
2. 有限状态机
确定的有穷状态机的模型如下：
确定的有穷自动机(DFA)定义为：A的五元组：\(A=(Q,\Sigma,\delta,q_0,F)\)。
- Q：有穷状态集
- \(\Sigma\)：有穷输入符号集或字母表
- \(\delta\)：\(Q\times \Sigma \to Q\)，状态转移函数
- \(q_0 \in Q\)：初始状态
- \(F \subseteq Q\)：终结状态集或接收状态集
状态转移图如下：
扩展转移函数
扩展\(\delta\)到字符串，定义扩展转移函数\(\hat \delta:Q \times \Sigma^* \to Q\)为： \[ \begin{equation} \hat \delta(q,w)= \begin{cases} q& \text{ $ w=\varepsilon $ } \\ \delta(\hat \delta(q,x),a)& \text{ $ w=xa $ } \end{cases} \end{equation} \] 其中\(a \in \Sigma, w,x \in \Sigma^*\)，那么当\(w=a_0a_1...a_n\)，则有\(\hat \delta(q,w)=\delta(\hat \delta(q,a_0a_1...a_{n-1}),a_n)...\)就这样一直嵌套递归下去。
DFA的语言与正则语言
定义：若\(D=(Q,\Sigma,\delta,q_0,F)\)是一个DFA,则D接受的语言为：\(L(D)=\left\{w \in \Sigma^*| \hat \delta(q_0,w) \in F\right\}\)
定义：如果语言L是某个DFA D的语言，即\(L=L(D)\)，则称L是正则语言。
非确定有穷自动机
非确定有穷自动机（NFA）的形式定义：
\(A=(Q,\Sigma,\delta,q_0,F)\)
- Q：有穷状态集
- \(\Sigma\)：有穷输入符号集或字母表
- \(\delta:Q\times \Sigma \to 2^Q\)状态转移函数
- \(q_0 \in Q\)：为初始状态
- \(F \subseteq Q\)：为终结状态集或接受状态集
DFA和NFA的等价性
定理1：如果L被NFA接受，当且仅当L被DFA接受。
非确定性并没有增加有穷自动机的能力。
带有空转移的非确定有穷自动机
空转移指的是不消耗字符串就能够进行转移的，空串\(\varepsilon\)。
定义为如下：
\(\varepsilon-NFA,NFA,DFA\)之间的主要区别：
- NFA,\(\varepsilon-NFA\)自动机在某状态读入某个字符时，可能有多个转移。
- \(\varepsilon-NFA,NFA,DFA\)在读入某个字符时，可能没有状态转移
- \(\varepsilon-NFA\)自动机在某状态，可能不读入字符就进行转移
状态的\(\varepsilon-\)闭包
状态q的\(\varepsilon-\)闭包记为\(E_{CLOSE}(q)\)，表示从q经过\(\varepsilon \varepsilon ... \varepsilon\)序列可达的全部状态集合，递归定义为：
- \(q \in E_{CLOSE}(q)\)
- \(\forall p \in E_{CLOSE}(q)\)，若\(r \in \delta(p, \varepsilon)\)，则\(r \in E_{CLOSE}(q)\)
3. 正则表达式
正则表达式的递归定义：
如果\(\Sigma\)为字母表，则\(\Sigma\)上的正则表达式递归定义为：
- \(\varPhi\)是一个正则表达式，表示空语言
- \(\varepsilon\)是一个正则表达式，表示语言\(\left\{\varepsilon\right\}\)
- \(\forall a \in \Sigma\)，a是一个正则表达式，表示语言\(\left\{a\right\}\)
- 如果正则表达式\(r\)和\(s\)分别表示语言R和S，那么\(r+s,rs,r^*,(r)\)都是正则表达式，分别表示语言：\(R \or S, R \cdot S,R^*,R\)
正则表达式的优先级：
- 首先括号优先级最高
- 其次\(r^*\)
- 然后是连接运算\(rs, r \cdot s\)
- 最后加最低\(r+s,r \or s\)
正则表达式示例：
- 定理：若\(L=L(A)\)是某DFA A的语言，那么存在正则表达式R满足\(L=L(R)\)