Формально об алгоритмах. Вычислительные модели/Задачи/ex-union-decideable-decideable — различия между версиями
Материал из DISCOPAL
| Строка 5: | Строка 5: | ||
''Начать распознавать входное слово <math>\omega</math>''<br /> | ''Начать распознавать входное слово <math>\omega</math>''<br /> | ||
:''Запустить машину <math>M_1</math> на входе <math>\omega</math>''<br/> | :''Запустить машину <math>M_1</math> на входе <math>\omega</math>''<br/> | ||
| − | :''Если <math>M_1</math> | + | :''Если <math>M_1</math> распознала <math>\omega</math>, тогда допускам <math>\omega</math>''<br/> |
:''Иначе''<br/> | :''Иначе''<br/> | ||
::''Запустить машину <math>M_2</math> на входе <math>\omega</math>''<br/> | ::''Запустить машину <math>M_2</math> на входе <math>\omega</math>''<br/> | ||
| − | ::''Если <math>M_2</math> | + | ::''Если <math>M_2</math> распознала <math>\omega</math>, тогда допускам <math>\omega</math>''<br/> |
::''Иначе <math>\omega</math> не распознана МТ''<br/> | ::''Иначе <math>\omega</math> не распознана МТ''<br/> | ||
Версия 13:46, 8 октября 2014
Маркеева Лариса 973б
Пусть есть язык , который распознается МТ и язык , который распознает МТ . Тогда машина которая распознает язык выглядит следующим образом.
Начать распознавать входное слово
- Запустить машину на входе
- Если распознала , тогда допускам
- Иначе
- Запустить машину на входе
- Если распознала , тогда допускам
- Иначе не распознана МТ
- Запустить машину на входе
Очевидно, что построенная нами МТ распознает , следовательно, он так же разрешимый. Значит, разрешимые языки замкнуты относительно операции объединения