本系列文章
有穷自动机正则表达式上下文无关文法和下推自动机图灵机正则表达式的递归定义：
ε \varepsilon ε 是一个正则表达式，表示语言 { ε } \{\varepsilon\} {ε} ; ϕ \phi ϕ 是一个正则表达式，表示空语言 ϕ \phi ϕ ; ∀ a ∈ Σ \forall a \in \Sigma ∀a∈Σ， a a a 是一个正则表达式, 表示语言 { a } \{a\} {a} ;如果 E E E 和 F F F 是正则表达式，表示的语言分别是 L ( E ) L(E) L(E) 和 L ( F ) L(F) L(F)，则 E + F , E F , E ∗ E+F,\;EF,\;E^* E+F,EF,E∗ 都是正则表达式，分别表示的语言是 L ( E ) ∪ L ( F ) , L ( E ) L ( F ) , ( L ( E ) ) ∗ L(E)\cup L(F),\; L(E)L(F),\;(L(E))^* L(E)∪L(F),L(E)L(F),(L(E))∗ ;如果 E E E 是正则表达式，则 ( E ) (E) (E) 也是。运算符优先级：括号 > 星 > 连接 > 加
每一个正则表达式都对应一个正则语言。
例： L = { w ∣ w ∈ 0 , 1 ∗ a n d w h a s n o p a i r o f c o n s e c u t i v e 0 ’ s } L=\{w\; |\; w \in { 0, 1 }^* \;and \;w \;has \;no \;pair \;of \;consecutive \;0’s \} L={w∣w∈0,1∗andwhasnopairofconsecutive0’s}
解： 1 ∗ ( 01 1 ∗ ) ∗ ( 0 + ε ) 1^* ( 0 1 1^* )^* ( 0 + \varepsilon) 1∗(011∗)∗(0+ε) 或 ( 1 + 01 ) ∗ ( 0 + ε ) (1+01)^*(0 + \varepsilon) (1+01)∗(0+ε)
练习：RegExp for ( Σ = { 0 , 1 } \Sigma=\{0,1\} Σ={0,1})
{w | w has exactly a single 1 }{w | w contains 001 }{w | length(w) ≥ 3 and the third symbol is 0 }What language does the RegExp ϕ ∗ \phi^* ϕ∗ represent ?正则表达式三种运算的转换：通过空转移
加：R+S
连接：RS
星：R*
例：将 (0+1)*1(0+1) 转化为FA
一些题目可以直接“看“出来，像这样：
状态消去法
但是题目太复杂了，容易丢三落四，于是使用状态消去法。过程如下：
然后每次消去一个状态，并将该状态表示的表达式添加在弧上 最后弧上得到的表达式就是该FA对应的正则表达式。
归纳法
将状态标记为 Q={1, 2, 3, …, n}
R i j ( k ) 其 中 0 ≤ k ≤ n R_{ij}^{(k)}\;其中0 \le k \le n Rij(k)其中0≤k≤n：i 到 j 路径的正则表达式，且路径上没有标记超过 k 的状态
过程：按照k=0，i=j 的公式算出不经过中间状态的正则表达式，然后递推套k≥1的公式就行。
泵引理用于证明某个语言不是正则的，它是正则语言应满足的必要条件
要证明是正则的可以使用构造DFA、NFA、ε-NFA、正则表达式的方法
正则语言的泵引理：假设 L 的是正则的，则 ∃ n \exists n ∃n，对 ∀ w ∈ L \forall w \in L ∀w∈L，若 ∣ w ∣ ≥ n |w|\ge n ∣w∣≥n，则可将 w 划分为 w = x y z w=xyz w=xyz，其中
∣ x y ∣ ≤ n |xy|\le n ∣xy∣≤n y ≠ ε ( ∣ y ∣ ≥ 1 ) y \ne \varepsilon (|y|\ge 1) y=ε(∣y∣≥1) ∀ k ≥ 0 , x y k z ∈ L \forall k\ge 0,\, xy^kz \in L ∀k≥0,xykz∈L例：证明 L = { 0 n 1 n ∣ n ≥ 0 } L=\{0^n1^n \, | \, n\ge 0\} L={0n1n∣n≥0} 不是正则的
解：假设它是正则的。由泵引理可知，一定存在一个常数n，对每个长度不小于n的 w ∈ L w\in L w∈L，可以被分成3的子串 w = x y z w=xyz w=xyz，且 ∣ x y ∣ ≤ n |xy|\le n ∣xy∣≤n， y ≠ ε y \ne \varepsilon y=ε， x y k z ∈ L xy^kz \in L xykz∈L
取 w = 0 n 1 n ∈ L w=0^n1^n \in L w=0n1n∈L，则 w = 0 n 1 n = x y z w=0^n1^n=xyz w=0n1n=xyz，由于 ∣ x y ∣ ≤ n |xy|\le n ∣xy∣≤n，故只能有 y = 0 m y=0^m y=0m，所以有 x z = 0 n − ∣ y ∣ 1 n ∈ L xz=0^{n-|y|}1^n \in L xz=0n−∣y∣1n∈L。
显然xz不是L中的字符串，所以矛盾，所以L不是正则的。
解题方法：上手先假设L是正则的，根据泵引理，选一个字符串w (最好是在开始的某个字符上重复了n次，即最开始是一个 a n a^n an)，然后就可以泵掉 |y| 个 a，然后就不属于L了，就推出矛盾
正则语言经某些运算后得到的新语言仍是正则语言，称正则语言在这些运算下封闭。
并： L ∪ M L \cup M L∪M交： L ∩ M L\cap M L∩M补： L ‾ \overline L L差： L − M L - M L−M反： L R L^R LR闭包(星)： L ∗ L^* L∗连接： L M LM LM同态： h : Σ ∗ → Γ ∗ h ( L ) = { h ( w ) ∣ w ∈ L } h:\; \Sigma^* \rightarrow \Gamma^*\qquad h(L)=\{ h(w)\, |\, w \in L \} h:Σ∗→Γ∗h(L)={h(w)∣w∈L}逆同态