正则语言

  把所有可以被正则表达式所定义的语言叫做正则语言(Regular Languages),则有一下定理

闭包性质

定理1

  如果L_1L_2是正则语言,则L_1+L_2L_1L_2L_1^\ast也是正则语言,这意味着所有正则语言构成的集合在(union),拼接(concatenation)和闭包(closure)操作下闭合

证明

  因为L_1L_2是正则语言,那么一定有对应的\footnotesize \Gamma_1\footnotesize \Gamma_2定义了他们,则有\footnotesize \Gamma_1+\footnotesize \Gamma_2定义了L_1+L_2\footnotesize \Gamma_1\footnotesize \Gamma_2定义了L_1L_2\footnotesize \Gamma_1^\ast定义了L_1^\ast
Q.E.D.

  不过,该定理还有另外一种证明方法,就是通过构造识别对应语言的自动机,不过这两者原则上都是基于Kleene定理,不再赘述。

补运算与交运算

  如果L\varSigma上的语言,定义L(complement)为\overline{L}(或L^\prime)由\varSigma中的字母组成的所有不在L中的字符串的集合,有\overline{\overline{L}}=L(集合论中补的运算法则,谨记语言本身是一个集合)

定理2

  如果L是一个正则语言,那么\overline{L}同样是正则语言,正则语言组成的集合在补运算下闭合

证明

  对于每个正则语言L都有一个对应的DFA识别,因此只需要构造把该DFA所有的停机状态都变为非停机状态(包括起始状态),所有非停机状态都变为停机状态(包括起始状态),这样在原DFA上被拒绝的字符串就会被接受,而原先被接受的字符串就会被拒绝,此时的DFA接受的语言恰巧是\overline{L}

定理3

  如果L_1L_2是正则语言,则L_1\cap L_2也是正则语言,也就是说正则语言的集合在(intersection)运算下闭合

证明

  根据德摩根定律,有

\begin{aligned}
\overline{L_1\cap L_2}&=\overline{L_1}\cup\overline{L_2}\\
L_1\cap L_2&=\overline{\overline{L_1}\cup\overline{L_2}}
\end{aligned}

而我们用到的+在这里表达的就是并的意思,也就是说

L_1\cap L_2=\overline{\overline{L_1}+\overline{L_2}}

根据定理1\overline{L_1}\overline{L_2}都是正则语言,\overline{L_1}+\overline{L_2}也是正则语言,因此\overline{\overline{L_1}+\overline{L_2}}也是正则语言

  该定理同样也有另一种证明方法,类比在Kleene定理的第三部分的第一个引理,也就是证明存在对应\footnotesize \Gamma_1+\footnotesize \Gamma_2的DFA的时候,当时根据识别\footnotesize \Gamma_1\footnotesize \Gamma_2的DFA构造了一个更大的DFA,识别被\footnotesize \Gamma_1\footnotesize \Gamma_2定义的语言,这里也可以如法炮制,惟一的区别是,当时FA_1FA_2对应的状态有任意一个是停机状态的话,结果就是停机状态,但是在这里,需要保证两个状态都是停机状态,最终结果才是停机状态。这样就构造了一个要求运行在其上的字符串既被FA_1识别,又被FA_2识别的自动机,也就是L_1\cap L_2对应的自动机


乱我心者,今日之日多烦忧