我知道问题是要为指定的图灵机提供证明。我的问题源于无法理解此问题所提议的结构类型,如下所示:
我们说语言类[[C]在操作⊕((L 1,L 2,…,L k)下关闭任何L 1,L 2,...,L k∈C,语言⊕(L 1,L 2, …,L k)在C中。
C
是具有某些属性(例如,可确定语言的属性)的所有对象的类。还要假设您有一个操作·
,它接受其中两个对象并返回另一个对象(数字2仅是示例)。我们说,在以下情况下,C
在·
下关闭:给定x
中的两个对象y
和C
,将运算符应用于它们也得到一个在C
中的对象:x · y \in C
。 (这只是您的问题中给出的定义)。例如,具有属性“它是一个布尔值” B
的对象的集合{ true, false }
在补码下关闭。对于b
中的任何值B
,补码! b
具有“它是一个布尔值”的属性,因此它也在B
中。因此,所有布尔值的集合B
在补码下都是封闭的。在这种情况下,证明可以是一张表,列出该操作输入的每种组合,并在每种情况下验证输出。
[另一个示例:属性为“它是从AZ起一个或多个字母的字符串”的所有对象的集合S
在连接时关闭:给定x
中的两个字符串y
和S
,串联x + y
也是一个字符串,因此它必须包含在属性为“它是一个或多个字母AZ的字符串”的对象的集合S
中。在这种情况下,证明可能是一个参数,用于根据对字符串的串联操作的定义来表明输出满足该属性。
标题中的问题要求您证明(证明)在互补运算,串联运算和交集运算下关闭了可确定语言的类别。也就是说:表明两种可确定语言的连接是一种可确定的语言,两种可确定语言的交集是一种可确定的语言,等等。