一 封闭性
正则语言之并是正则的
正则语言之交是正则的
用自动机的乘积自动机。
如果证明了3，也可以用集合运算。
正则语言的补语言是正则的
用一个 DFA 表示原来的语言，然后把非接受状态改为接受状态，把接受状态改为非接受状态。
正则语言的差是正则的
集合运算。
正则语言的反转是正则的
用一个 DFA A 表示原来的语言，把 A 改造成 RA, 先把所有箭头反转；把接受状态改为普状态；把初始状态改为接受状态。加入一个新状态作为初始状态，并发出 e 箭头指向原来的全体接受状态。
另一种方法是归纳。设语言为 L(A)，则 R(L(A)) = L(R(A))
正则语言的 kleene 闭包是正则的
正则语言的连接是正则的
二 应用举例
设字符集合为 {0,1}. 语言 L 表示由不同个数的 0,1 组成的串, 试证明其为非正则的.
用泵引理证明 L 的补语言 L'={0,1 个数相同的串} 是非正则的. 从而 L' 的补语言 L 是非正则的.
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024