正则表达式

递归定义

1. $\empty$是一个正则表达式，表示空语言$\empty$
2. $\varepsilon$是一个正则表达式，表示语言$\{\epsilon\}$
3. 对任意一个符号$a$，$a$是一个正则表达式，表示语言$\{a\}$，其有一个长度为 1 的字符串
4. 如果$E_1$、$E_2$是正则表达式，那么$E_1+E_2$也是正则表达式，且$L(E_1+E_2)=L(E_1)\cup L(E_2)$
5. 如果$E_1$、$E_2$是正则表达式，那么$E_1E_2$也是正则表达式，且$L(E_1E_2)=L(E_1)L(E_2)$
6. 如果$E$是正则表达式，那么$E^*$也是正则表达式
7. 如果$E$是正则表达式，那么$(E)$也是正则表达式，表示语言$L(E)$

运算符的优先级

1. $()$优先级最高
2. $E^*$
3. $E_1E_2$
4. $E_1+E_2$

示例

$(a+b)^(a+bb)$：$L((a+b)^(a+bb))=\{w|w\text{仅由a和b组成，仅以a或者bb结尾}\}$

有穷自动机和正则表达式

自动机和正则表达式的关系