正则语言
Howard Yin 2020-11-15 09:31:05 数学形式语言与自动机计算理论正则表达式
!!注意正则语言和正则表达式之间的区别与联系!!
正则语言的定义
若语言L是某个DFAD的语言,则称L是正则语言:
L是正则语言⇔(∃D=(Q,Σ,δ,q0,F))(L=L(D))
自动机理论中的典型问题
任何问题都能转化为语言的成员性问题:判断给定的字符串w是否属于某个具体的语言L
w∈L?
正则表达式与DFA和正则语言间的等价性
⇒正则表达式与DFA等价正则表达式与正则语言等价正则表达式章节中已经证明正则语言定义
正则语言的封闭性
- ∅、{ε}都是正则语言
- Σ∗、Σ+是字母表Σ上的正则语言
- (正则运算)若L和M都是正则语言,则:
- (交运算)M是正则语言
- (并运算)L∪M是正则语言
- (差运算)L−M是正则语言
- (补运算)L=Σ∗−L是正则语言
- (连接运算)LM是正则语言
- (闭包运算)L∗是正则语言
- (反转运算)若L是正则语言,则LR={wR∣w∈L}是正则语言
- 其中wR=(a1a2…an)R=an…a2a1
- (同态)若L是正则语言,则h(L)是正则语言
- 其中h(L)称为语言L的同态,定义如下:
- 当输入为字母a∈Σ时,h:Σ→Γ∗是一个从字母表Σ到另一个字母表上闭包Γ∗的映射
- 当输入为字符串w∈Σ∗时:h(ε)=ε,h(wa)=h(w)h(a)
- 当输入为语言L⊆Σ∗时:h(L)={h(w)∣w∈L}
- (逆同态)若L是正则语言,h−1(L)={w∈Σ∗∣h(w)∈L}是正则语言
证明略。
正则语言的必要条件:泵引理
对于任意正则语言,总能找到一个正整数N(泵长度),该语言中所有长度大于N的字符串w可以分为w=xyz三部分,其中中间的y满足:
- y非空
- y在前N个字符内
- y可以不断重复而产生新串xykz,且产生的所有串都仍然属于该语言
(理解“泵”:通过中间的字符串y不断产生新串,就像泵一样)
L是正则语言⇒(∃N∈N+)(∀w∈L)(∣w∣≥N→(∃y=ε,∣xy∣<N)(∀k≥0)(xykz∈L))
证明
令N为DFAA的状态数,L=L(A),分两种情况讨论:
1' (∀w∈L)(∣w∣<N)
显然(∣w∣≥N→(∃y=ε,∣xy∣<N)(∀k≥0)(xykz∈L))成立,因为没有∣w∣≥N的情况
2' (∃w∈L)(∣w∣≥N)
- 任取一个∣w∣≥N
- 设m=∣w∣,w=a1a2…am,令qi=δ^(q0,a1a2…ai)表示DFA识别此字符串时读入字符ai所到达的状态。
- 由于m≥N,加上初始状态一共N+1个状态,因此必然存在两个状态相等:(∃0≤i<j≤N)(qi=qj)
- 令:
- x=a1a2…ai−1(i≥1)或x=ε(i=0)
- y=aiai+1…aj
- z=aj+1aj+2…am(j≤m−1)或x=ε(j=m)
- 由于qi=qj,因此让DFA在qiqi+1…qj之间不断循环可以对应出无穷多个字符串,即xykz
泵引理即证。
案例
由正则表达式和正则语言的形式和定义显而易见,正则表达式可以作为正则语言的一种简化的表示方法,在给正则表达式加上一些非正则的操作(例如下面的∑n=0∞)后也可以用来表示一些非正则语言。一般以粗体表示正则表达式,大写字母表示语言。
证明语言L=∑n=0∞0n1n={0n1n∣n≥0}不是正则语言
反证法:
- 假设L是正则的,那么它满足泵引理
- 取w=0N1N∈L,它显然满足∣w∣=2N≥N
- 那么对于y=ε,∣xy∣<N:
- y只能取前N项
- w=0N1N前N项全是1
- 因此y=0m,0<m<N
- 那么xy2z=0N+m1N∈/L矛盾
- 因此L不满足泵引理,不是正则语言
证明语言L={w∣w由数量相等的01构成}不是正则语言
同理,用反证法:
- 假设L是正则的,那么它满足泵引理
- 取w=0N1N∈L,它显然满足∣w∣=2N≥N
- 同理可以引出xy2z=0N+m1N∈/L矛盾
- 因此L不满足泵引理,不是正则语言
证明语言L={0i1j∣i>j}不是正则语言
同理,用反证法:
- 假设L是正则的,那么它满足泵引理
- 取w=0N+11N∈L,它显然满足∣w∣=2N+1≥N
- 同理可以引出y=0m,0<m<N
- 那么xy0z=0N+1−m1N∈/L矛盾
- 因此L不满足泵引理,不是正则语言
∑n=0∞0n1n和∑n=01000n1n:由非正则语言引发的思考
由上面的第一个案例可以看出,尽管都完全由正则运算构成,∑n=0∞0n1n不是正则语言,而对于语言∑n=01000n1n,∑n=01000n1n本身就是它的正则表达式,它是正则语言。完全由正则的求和运算运算组成的运算扩展到无穷成为∑n=0∞就不是一个正则运算了。
由此我们可以直觉上感觉到DFA的和正则语言的能力限制:“有穷自动机”的“有穷”决定了有穷自动机只能保存有限个状态,而∑n=0∞0n1n这类语言要求自动机记住无穷多个“状态”(记住0的数量并将之与1的数量进行比较,数量最多可以是无穷多个),因此有穷自动机不能识别。
另外,对于字符串数量有限的语言,必定(∃N∈N+)(∀w∈L)(∣w∣<N),即泵引理必然成立,而其自身也总可以表示为有限个正则表达式的和,因此字符串数量有限的语言必然是正则语言,更加印证了我们对有穷自动机中“有穷”的直觉把握。
那么与有穷自动机相对的,是否存在“无穷自动机”?请见下推自动机。