Покажите, что класс разрешимых языков закрыт для операций: Комплементация, Конкатенация и Пересечение

Question

Я понимаю, что проблема заключается в запросе доказательства для указанной машины Тьюринга. Моя проблема проистекает из неспособности понять, какой тип структуры предлагает эта проблема, как указано ниже:

---

Мы говорим, что класс C языков закрыт операция 100 (L ₁ , L ₂ ,…, L _k ) если для любого L ₁ , L ₂ ,…, L _k ∈ C, язык ⊕ (L ₁ , L ₂ ,…, L _k ) в C.

---

Может кто-нибудь, пожалуйста, объясните мне, что это значит

Answer 1

Множество закрыто для операции над элементами этого множества тогда и только тогда, когда гарантируется, что результат применения операции к элементам множеств создаст другой элемент множества. Таким образом, набор натуральных чисел (неотрицательных целых чисел) при сложении закрыт, поскольку добавление любых двух натуральных чисел приводит к получению другого натурального числа. Множество натуральных чисел не вычитается при вычитании, поскольку некоторые различия (например, 10 - 20) не являются натуральными числами.

Чтобы показать три вещи, которые вас просят сделать, вы можете рассуждать следующим образом:

1. Комплементация: поскольку возможность принятия решения означает, что вы можете ответить «да» или «нет» на вопрос о членстве за конечное время для всех строк-кандидатов, набор решаемых языков должен быть закрыт при дополнении, поскольку вы можете просто поменять местами ответы «да» "и" нет ", чтобы получить решающее слово для дополнения любого разрешимого языка.
2. Конкатенация: если у вас есть решатели для двух решаемых языков, то вы можете получить решающее слово для объединения этих языков, недетерминированно угадав в сначала решите, когда вы прочитали часть строки с первого языка, а затем проверьте, является ли остаток строкой на втором языке. Недетерминированные c ТМ не более мощны, чем обычные ТМ, поэтому здесь нет проблем.
3. Пересечение: аналогично объединению, за исключением того, что вы просто запускаете оба решателя во входной строке и отвечаете да, если оба ответили да, нет иначе.

Мы описали конструкции, которые показывают, что применение этих операций к разрешаемым языкам приводит к разрешаемым языкам. Это означает, что под этими операциями закрывается множество разрешимых языков.

Answer 2

Предположим, что C - это класс всех объектов, которые имеют какое-либо свойство (например, свойство быть разрешимым языком). Также предположим, что у вас есть операция ·, которая берет два из этих объектов и возвращает другой объект (число два - просто пример). Мы говорим, что C закрывается в ·, когда: если дано два объекта x и y в C, применение к ним оператора дает объект, который также находится в C: x · y \in C. (Это просто определение, приведенное в вашем вопросе.)

Например, набор B объектов со свойством «это логическое значение» { true, false } закрывается при дополнении. Для любого значения b из B дополнение ! b имеет свойство «это логическое значение», поэтому оно также находится в B. Таким образом, множество B всех логических значений закрыто для дополнения. В этом случае доказательством может быть таблица, в которой перечислены все комбинации входных данных для операции и проверены выходные данные в каждом случае.

Другой пример: набор S всех объектов, имеющих свойство «это строка из одной или нескольких букв из AZ "закрыта при конкатенации: для любых двух строк x и y в S конкатенация x + y также является строкой, поэтому она должна содержаться в наборе S объектов, которые имеют свойство «это строка из одной или нескольких букв AZ». В этом случае доказательством может быть аргумент, показывающий, что вывод удовлетворяет свойству, основанному на определении операции конкатенации строк.

В вопросе заголовка предлагается показать (доказать), что класс разрешимых языков закрывается в операции дополнения, в операции конкатенации и в операции пересечения. То есть: показать, что конкатенация двух разрешимых языков является разрешимым языком, что пересечение двух разрешимых языков является разрешимыми языками и т. Д. c.