正则语言的性质
- 如何判定一个语言是否是正则语言？
- 一个正则语言可以有多种描述形式，能否找到最小的一个DFA？
正则语言的泵引理¶
如何证明一个语言L不是正则语言？
正向证明是十分困难的，需要证明没有任何一个DFA或者NFA能够接受L
可以使用泵引理进行证明
鸽巢原理（抽屉原理）¶
如果把每只鸽子都放到鸽巢中，那么必定有一个鸽巢当中存在至少两只鸽子
泵引理¶
如果语言L是正则的，那么存在正整数N，对\(w\in L\)，只要\(|w|≥N\)，就可以将w分成三部分w=xyz，满足：
- |y|>0
- |xy|≤N
- \(\forall k≥0,xy^kz\in L\)
可以理解为：一个有N个状态的路径，任何从开始状态到接收状态的路径，如果长度超过N，那么一定会经过N+1个状态，那么必定会有一个重复状态，因此可以形成一个循环，多次经过这个循环后仍然可以沿着原路径到达接收状态
泵引理可以用来确定特定语言不是正则语言，泵引理是判定正则语言成立的必要条件，而非充分条件
例：证明\(L=\{a^{n!}|n>0\}\)
有限的语言必定是正则语言，取N为有限语言最长字符串长度+1，不存在\(w\in L(|w|≥N)\)
封闭原理¶
正则语言在经过一些运算后仍然可以保持新语言正则
- 并
- 交
- 反转
- 同态
- 逆同态
- 补
- 差
同态：若\(\Sigma\)和\(\Gamma\)是两个字母表，同态定义为函数\(h:\Sigma\to\Gamma^*\)（将\(\Sigma\)上的一个符号映射为\(\Gamma\)上的符号串）
\[\forall a\in \Sigma,h(a)\in \Gamma^*\]扩展h定义至字符串：
\[\begin{split}h(\epsilon)=\epsilon\\h(xa)=h(x)h(a)\end{split}\]在扩展到语言，对\(\forall L\subseteq \Sigma^*\)
\[h(L)=\{h(w)|w\in L\}\]
交运算¶
若DFA \(A_L,A_M和A\)的定义如下：
其中\(\delta((p,q),a)=(\delta_L(p,a),\delta_M(q,a))\)
对于任意\(w\in \Sigma^*,\hat{\delta}((q_L,q_M),w)=(\hat{\delta}(q_L,w),\hat{\delta}(q_M,w))\)
例：\(L_1:1*0(0+1)*\quad L_2:0*1(0+1)*\)，求\(L_1\cap L_2\)
定理：如果\(L_1,L_2\)都是正则语言，那么\(L_1\cap L_2\)一定是正则语言
假如\(L_1,L_2\)都不是正则的，\(L_1\cap L_2\)也不一定就是非正则语言
例：\(L_1=\{0^n1^n|n>0\}\quad L_2=\{a^nb^n|n>0\}\),两者的交为\(L_1\cap L_2=\{\epsilon\}\)是正则语言
判定性质¶
3个典型的判定问题¶
- 以某种形式化模型描述的语言是否为空? 是否无穷?
- 某个特定的串w是否属于所描述的语言?
- 以两种方式描述的语言, 是否是相同的? — 语言的等价性。
定理¶
- 具有n个状态机的有穷自动机M接受的集合S
- S是非空的，当且仅当M接受某个长度小于n的串
- S是无穷的，当且仅当M接受某个长度为m的串，n≤m≤2n