1.63

2024-10-01

 

题目

a. Let be an infinite regular language. Prove that can be split into two infinite disjoint regular subsets.

b. Let and be two languages. Write if and contains infinitely many strings that are not in . Show that if and are two regular languages where , then we can find a regular language where .

思路

点击展开

a. 正则语言的无限性可以看作来自 DFA 的回路，通过规定通过回路的方式，可以将无限性分为多份

b. 在第一问的铺垫下，思路显然

解答

点击展开

a. 为了将正则语言分为 个无穷的部分，我们记字符串经过 DFA 中状态的总次数记为 ，并将 作为标记，添加接受字符串的额外条件：，就构成了 个新的 DFA，形式化的构造显然，不赘述。由于经过回路的次数是任意的，所以这些新的 DFA 都对应无穷的正则语言。

b. 将 依 a 划分为 个无穷正则子集

评论区

最新评论

--