Формально об алгоритмах. Вычислительные модели/Задачи/ex-union-decideable-decideable — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | + | Маркеева Лариса 973б | |
| − | + | ||
| − | + | ||
| − | + | Пусть есть язык <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> accept <math>\omega</math>, тогда допускам <math>\omega</math>''<br/> | ||
| + | :''Иначе''<br/> | ||
| + | ::''Запустить машину <math>M_2</math> на входе <math>\omega</math>''<br/> | ||
| + | ::''Если <math>M_2</math> accept <math>\omega</math>, тогда допускам <math>\omega</math>''<br/> | ||
| + | ::''Иначе <math>\omega</math> не распознана МТ''<br/> | ||
| + | |||
| + | Очевидно, что построенная нами МТ распознает <math>L_1\cup L_2</math>, следовательно, он так же разрешимый. Значит, разрешимые языки замкнуты относительно операции объединения | ||
| + | |||
| + | [[Категория:На проверку]] | ||
Версия 13:45, 8 октября 2014
Маркеева Лариса 973б
Пусть есть язык , который распознается МТ и язык , который распознает МТ . Тогда машина которая распознает язык выглядит следующим образом.
Начать распознавать входное слово
- Запустить машину на входе
- Если accept , тогда допускам
- Иначе
- Запустить машину на входе
- Если accept , тогда допускам
- Иначе не распознана МТ
- Запустить машину на входе
Очевидно, что построенная нами МТ распознает , следовательно, он так же разрешимый. Значит, разрешимые языки замкнуты относительно операции объединения