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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 15 промежуточных версий этого же участника)
Строка 1: Строка 1:
Маркеева Лариса 973б
+
<latex>
 +
Докажите, для разрешимых языков $L_1$ и $L_2$, язык $L=L_1 \cup L_2$ также разрешим.
 +
</latex>
  
Пусть есть язык <math>L_1</math>, который распознается МТ <math>M_1</math> и язык <math>L_2</math>, который распознает МТ <math>M_2</math>. Тогда машина <math>M</math> которая распознает язык <math>L_1\cup L_2</math> выглядит следующим образом.
 
  
''Начать распознавать входное слово <math>\omega</math>''<br />
+
<!--Вообще-то, решения уже есть-->
:''Запустить машину <math>M_1</math> на входе <math>\omega</math>''<br/>
+
:''Если <math>M_1</math> распознала <math>\omega</math>, тогда допускам <math>\omega</math>''<br/>
+
:''Иначе''<br/>
+
::''Запустить машину <math>M_2</math> на входе <math>\omega</math>''<br/>
+
::''Если <math>M_2</math> распознала <math>\omega</math>, тогда допускам <math>\omega</math>''<br/>
+
::''Иначе <math>\omega</math> не распознана МТ''<br/>
+
  
Очевидно, что построенная нами МТ распознает <math>L_1\cup L_2</math>, следовательно, он так же разрешимый. Значит, разрешимые языки замкнуты относительно операции объединения
+
[[Категория:Решенные задачи]]
 
+
[[Категория:На проверку]]
+

Версия 13:57, 8 апреля 2020