正则表达式
Howard Yin 2020-12-23 07:54:03 数学形式语言与自动机计算理论正则表达式
!!注意正则语言和正则表达式之间的区别与联系!!
正则表达式的定义
字母表Σ上的正则表达式以递归方式定义:
- (基础)空集∅是正则表达式,表示空语言
- (基础)ε是正则表达式,表示语言{ε}
- (基础)∀a∈Σ,a是正则表达式,表示语言{a}
- (递归)如果r、s都是正则表达式,分别表示语言L和M,那么:
- (并运算)r+s是正则表达式,表示语言L∪M
- (连接运算)rs是正则表达式,表示语言LM
- (闭包运算)r∗是正则表达式,表示语言L∗
- (改变运算优先级)(r)是正则表达式,表示语言L
正则表达式与DFA和正则语言间的等价性
为了简便起见,这里分别证明“任意DFA的语言都可以由一个正则表达式所表示”和“任意正则表达式的语言都可以由一个ε-NFA所识别”。
有了这两条性质,显而易见正则表达式与DFA和正则语言间的等价性:
{任意DFA的语言都可以由一个正则表达式所表示任意正则表达式的语言都可以由一个ε-NFA所识别⇒正则表达式与DFA等价⇒正则表达式与正则语言等价在下面证明DFA与ε-NFA等价正则语言定义
任意DFA的语言都可以由一个正则表达式所表示
原命题可以描述为:
(∀A是DFA)(∃正则表达式R)(L(A)=L(R))
此式显然成立,因为对于任意的语言L,我们只需要:
- (∀l=a1a2…an∈L)El=a1a2…an={a1a2…an}:用连接运算对语言中的每个字符串构造一个正则表达式
- E=⋃l∈LEl=⋃a1a2…an∈L{a1a2…an}=L:对所有这些正则表达式进行并运算即可得要构造的语言
DFA的语言当然也能构造出来。
注:实际计算中当然不可能遍历所有字符串,具体使用的构造方法有递归式法、状态消除法等。
任意正则表达式的语言都可以由一个ε-NFA所识别(由正则表达式构造ε-NFA的方法)
按照正则表达式的定义,用递归的方式进行证明。
对于字母表Σ上的正则表达式:
- (基础)正则表达式∅对应的ε-NFA显然是对任何输入都不能跳转到接受状态的ε-NFA:
- (基础)正则表达式ε对应的ε-NFA显然是一个空转移就跳转到接受状态的ε-NFA:
- (基础)∀a∈Σ,正则表达式a={a}对应的ε-NFA显然是读取字符a就跳转到接受状态的ε-NFA:
- (递归)如果r、s都是正则表达式,分别对应一个ε-NFA,那么可以指定一个起点和终点,其中指定的起点通过空转移到ε-NFA内的起点、ε-NFA内的终点空转移到指定的终点,构造如下ε-NFA:
那么:
- (并运算)正则表达式r+s等价于并联它们就行:
- (连接运算)正则表达式rs等价于串联它们:
- (闭包运算)正则表达式r∗等价于首尾相连:
- (改变运算优先级)正则表达式(r)等价于原ε-NFA不变。
由此,所有的正则表达式均可一步步构造出一个ε-NFA进行表示,原命题得证。
正则表达式的运算规则
运算优先级定义
括号>闭包运算>连接运算>并运算。例如1+01∗=1+(0(1∗))
一些正则表达式计算规则
并运算连接运算分配律闭包运算结合律交换律幂等律单位元∅结合律单位元ε零元∅左分配律右分配律(r+s)+tr+sr+r∅+r(rs)trεr∅rsr(s+t)(r+s)t(r∗)∗∅∗ε∗r∗(ε+r)∗=r+(s+t)=s+r=r=r+∅=r=r(st)=εr=∅r=∅=sr=rs+rt=rt+st=r∗=ε=ε=r++ε=r∗
一些化简规则
(ε+r)r∗r+rs∗=r∗=rs∗
示例
E | L(E) |
a+b | {a}∪{b}={a,b} |
(a+b)(a+b) | {a,b}{a,b}={aa,ab,ba,bb} |
(a+b)∗(aa+bb) | {a,b}∗{aa,bb}={以aa或bb结尾的字符串} |
1+01∗ | {ε,1,01,0101,010101,…} |
(0+1)∗01 | {w∈{0,1}∗∣w以01结尾} |
01(0+1)∗+(0+1)∗01 | {w∈{0,1}∗∣w以01开头或以01结尾} |
(0+1)∗(1+10+100) | {w∈{0,1}∗∣w最后三个字符至少有一个是1} |