8. 正则语言的闭包性质¶
8.1. 闭包概念¶
形式语言领域中一个重要的问题是：给定的语言是否为正则语言。 当然，如果我们能构造一个识别它的 DFA 或 NFA，或者写出一个表示它的 正则表达式或正则文法，那么它就是正则语言。 但有时我们可能难以直接做到这一点。 工具箱中的另一个工具是：借助一个或多个已知为正则的语言来描述目标语言， 这些语言通过某个已知对正则语言集合封闭（closed）的运算进行组合或改造。 在本模块中，我们将证明若干运算对正则语言集合是封闭的。
定义： 一个集合对二元运算是 封闭 的，如果每当 该运算作用于集合中任意两个成员时，结果仍是该集合的成员。 一个集合对一元运算是封闭的，如果该运算作用于集合中任意一个成员时， 结果仍是该集合的成员。
8.2. 正则语言的闭包性质——基本运算¶
8.3. 右商¶
8.4. 同态¶
8.5. 关于正则语言的一些可判定问题¶
8.6. 小结：如何证明一个语言是正则语言？¶
我们刚刚讨论了一组我们已知如何回答的、与正则语言相关的问题。 那么，关于一个语言，我们能提出的最重要的问题（至少就正则语言这一语境 而言）是什么呢？ 如果我向你描述一个语言（例如用英语），这个语言是正则语言吗？ 这是一个实际问题，因为如果已知一个语言是正则的，我们就有办法 形式化地定义它。 这意味着该语言的关键应用（比如判断给定串是否属于该语言） 可以在计算机上实现。 因此，证明一个语言是正则语言的一个基本方法，就是用下列方法之一实现它：
写出一个接受该语言的 DFA。
写出一个接受该语言的 NFA。
写出一个描述该语言的正则表达式。
写出一个描述该语言的正则文法。
证明语言是正则语言的一个稍微间接的方法，是借助一个或多个 已知的正则语言来定义它，而这些正则语言是用已知对正则语言封闭的 运算符来处理和改造的。 这正是我们花了一些时间来定义一组有用的此类运算符的原因。
这引出了若干问题！ 是否存在 不是 正则的语言？ 如果是这样，我们又该如何证明一个语言是否为正则语言呢？ 请注意，上面列表中的每一项都是构造或模拟。 我们也可能无法像用构造证明语言 确实 具有某个性质那样， 用构造证明语言 并非 具有某个性质。 用于证明语言不是正则语言的一些技巧，是下一章的话题。 剧透预警：遗憾的是，我们将看到，我们并没有总能证明一个语言是否 为正则语言的确定性方法。 我们只是拥有一些工具，它们有时让我们证明该语言是正则的（通常通过构造 上文已描述的某一种表示），有时则让我们证明该语言不是正则的。 .. odsascript:: DataStructures/PIFrames.js .. odsascript:: AV/PIFLA/Regular/ClosureConceptFS.js .. odsascript:: AV/PIFLA/Regular/RLClosPropFS.js .. odsascript:: DataStructures/FLA/FA.js .. odsascript:: AV/PIFLA/Regular/RLClosQuotientFS.js .. odsascript:: AV/PIFLA/Regular/RLHomomorphFS.js .. odsascript:: AV/PIFLA/Regular/RLQuestionsCON.js
