证明正则操作是封闭的

Posted by persuez on June 8, 2018

以下证明均用NFA证明,以下证明均只说证明思路,没有严格的数学论证。

正则语言在并操作中是封闭的。(The class of regular languages is closed under the union operation.)

思路:我们有两个正则语言$A_1$和$A_2$,并且想要证明$A_1 \cup A_2$也是正则语言。我们证明的思路是有两个NFA$N_1$和$N_2$分别识别语言$A_1$和$A_2$,我们现在要构造一个NFA$N$来识别$A_1 \cup A_2$。

我们要设计$N$使得:如果$N_1$或$N_2$接受了输入,那么机器$N$也要接受该输入。在NFA中,要构造这种机器是相当容易的,只要新增一个开始状态,并用$\epsilon$分别“映射”到$N_1$和$N_2$的开始状态就可以了。下图可以直白的看出构造: union图

正则语言在连接操作中是封闭的。(The class of regular languages is closed under the concatenation operation.)

思路:我们有两个正则语言$A_1$和$A_2$,并且想要证明$A_1 \circ A_2$也是正则语言。我们证明的思路是有两个NFA$N_1$和$N_2$分别识别语言$A_1$和$A_2$,我们现在要构造一个NFA$N$来识别$A_1 \circ A_2$。

我们要设计$N$使得:如果$N_1 \circ N_2$接受了输入,那么机器$N$也要接受该输入。在NFA中,要构造这种机器是相当容易的,只要将$N_1$的所有接受状态变为普通状态,通过$\epsilon$“映射”到$N_2$的开始状态即可。下图可以直白的看出构造: concatenation图

正则语言在闭包操作中是封闭的。(The class of regular languages is closed under the star operation.)

思路:我们有正则语言$A_1$,并且想要证明$A_1^\star$也是正则语言。我们证明的思路是有一个NFA$N_1$识别$A_1$,我们将修改它使其能够识别$A_1^\star$。

这次构造$N$分为两步:

  1. 将$N_1$的接受状态通过$\epsilon$连接到开始状态,初步形成闭包。
  2. 这一步的目的是使$N$接受$\epsilon$。粗糙地,也许你会想直接使开始状态变为接受状态就可以了,但是这样是错误的。例如$N_1$为: 闭包错误构造样例 本来这个NFA接受的是以a开头并以b结尾的字符串,但如果像上述做法,那这个NFA也可以接受如以字符a结尾的字符串,这样的语言已经不是$A_1^\star$了。那我们的正确做法是新增一个开始状态,并且该开始状态是属于接受状态集合的。具体图如下: 闭包正确构造