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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 16 промежуточных версий этого же участника)
Строка 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>, следовательно, он так же разрешимый. Значит, разрешимые языки замкнуты относительно операции объединения
+
[[Категория:Решенные задачи]]
−
 
+
[[Категория:Теоретические задачи]]
−
[[Категория:На проверку]]
+

Текущая версия на 06:50, 4 мая 2023

Источник — «https://discopal.ispras.ru/index.php?title=Формально_об_алгоритмах._Вычислительные_модели/Задачи/ex-union-decideable-decideable&oldid=25857»