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

Ссылки сюда (13) →

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

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

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

Запустить машину на входе

Если accept , тогда допускам

Иначе

Запустить машину на входе

Если accept , тогда допускам

Иначе не распознана МТ

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

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

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

---

— Девицкий Иван 375 • 13 мая 2016 в 22:41

• страница

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