computer-science - 证明可判定语言类在以下操作下是封闭的：互补、连接和交集

Question

我知道问题是要求为指定的图灵机提供证明。我的问题源于无法理解此问题提出的结构类型，如下所示：

---

我们说一个语言类C在操作 ⊕<strong>(L ₁ ,L ₂ ,...,L _k )下是封闭的，如果对于任何L ₁ ,L ₂ ,...,L _k ∈C，语言 ⊕<strong >(L ₁ ,L ₂ ,…,L _k ) 在C中。

---

有人可以向我解释这是什么意思吗？

标签： computer-sciencediscrete-mathematicsproofcomputation-theoryturing-machines

Answer 1

假设它C是具有某种属性（例如，作为可判定语言的属性）的所有对象的类。还假设您有一个操作·，它采用其中两个对象并返回另一个对象（第二个只是一个示例）。我们说在 when:C下是封闭的·：给定两个对象x和yin C，将运算符应用于它们会给出一个对象，该对象也在C:中x · y \in C。（这只是您的问题中给出的定义）。

例如，B具有“它是一个布尔值”属性的对象集{ true, false }在互补下是封闭的。b对于来自的任何值B，补码! b具有“它是布尔值”的属性，因此它也在B. 所以B所有布尔值的集合在互补下是封闭的。在这种情况下，证明可以是一个表格，列出操作的每个输入组合，并在每种情况下验证输出。

另一个例子：S具有属性“它是来自AZ的一个或多个字母的字符串”的所有对象的集合在连接下是封闭的：给定任意两个字符串x和yin S，连接x + y也是一个字符串，所以它必须包含在S具有“它是一个或多个字母 AZ 的字符串”属性的对象集。在这种情况下，证明可能是一个参数，表明输出满足基于字符串连接操作定义的属性。

标题中的问题要求你展示（证明）可判定语言类在补运算、串联运算和交集运算下是封闭的。即：表明两种可判定语言的连接是一种可判定语言，两种可判定语言的交集是一种可判定语言，等等。