正则表达式

• $\Sigma$
• $\Sigma^*$

定义

R是正则表达式，当且仅当R是

• $a, a\in\Sigma$
• $\epsilon$
• $\empty$
• $(R_1\cup R_2)$
• $(R_1R_2)$
• $({R_1}^*)$

L(R)

• 归纳定义

• 省略括号

  • 最外层
  • 规定优先级：星号>连接>并

• $R\cup\empty=R$

• $R\epsilon=R$

  • 一般 $R\empty\ne R,R\cup\epsilon\ne R$

• $R\cup\epsilon=R\cup\{\epsilon\}$

• $R\empty=\empty$

正则表达式与自动机等价性

• 一个语言是正则的 当且仅当 可用正则表达式描述这个语言
• 正则表达式描述正则语言
  • 证明思路：转换成NFA
• 正则语言可用正则表达式描述

GNFA

GNFA: 广义NFA

• 箭头标号是正则表达式
• 初始状态
  • 唯一
  • 有到所有其他状态的箭头
  • 所有其他状态都没有到他的箭头
• 接受状态：
  • 唯一

非正则语言

泵引理：设A是正则语言，则存在常数p（称为泵长度），使得若$s\in A$且$|s|\ge p$，则$s=xyz$，并且满足下述条件

1. $\forall i\ge0,xy^iz\in A$
2. $|y|>0$
3. $|xy|\le p$

反证法，先假设正则，再推出来不合理