显示可决定的语言类别在以下操作下是互补的:补全,串联和交集

问题描述 投票:-2回答:1

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


我们说语言类[[C]在操作⊕((L 1,L 2,…,L k下关闭任何L 1,L 2,...,L k∈C,语言⊕(L 1,L 2, …,L k)在C中。


有人可以告诉我这是什么意思吗?
computer-science discrete-mathematics proof computation-theory turing-machines
1个回答
0
投票
假设C是具有某些属性(例如,可确定语言的属性)的所有对象的类。还要假设您有一个操作·,它接受其中两个对象并返回另一个对象(数字2仅是示例)。我们说,在以下情况下,C·下关闭:给定x中的两个对象yC,将运算符应用于它们也得到一个在C中的对象:x · y \in C。 (这只是您的问题中给出的定义)。

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

[另一个示例:属性为“它是从AZ起一个或多个字母的字符串”的所有对象的集合S在连接时关闭:给定x中的两个字符串yS ,串联x + y也是一个字符串,因此它必须包含在属性为“它是一个或多个字母AZ的字符串”的对象的集合S中。在这种情况下,证明可能是一个参数,用于根据对字符串的串联操作的定义来表明输出满足该属性。

标题中的问题要求您证明(证明)在互补运算,串联运算和交集运算下关闭了可确定语言的类别。也就是说:表明两种可确定语言的连接是一种可确定的语言,两种可确定语言的交集是一种可确定的语言,等等。

© www.soinside.com 2019 - 2024. All rights reserved.