Формально об алгоритмах. Вычислительные модели/Задачи/ex-union-decideable-decideable

Материал из DISCOPAL
Перейти к: навигация, поиск

Маркеева Лариса 973б

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

Начать распознавать входное слово

Запустить машину на входе
Если accept , тогда допускам
Иначе
Запустить машину на входе
Если accept , тогда допускам
Иначе не распознана МТ

Очевидно, что построенная нами МТ распознает , следовательно, он так же разрешимый. Значит, разрешимые языки замкнуты относительно операции объединения

[ Хронологический вид ]Комментарии

  • Формально об алгоритмах. Вычислительные модели/Задачи/ex-union-decideable-decideable

Войдите, чтобы комментировать.