|
|
| Строка 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> выглядит следующим образом.
| + | [[Category:Решенные задачи]] |
| − | | + | <!--Вообще-то, решения уже есть--> |
| − | ''Начать распознавать входное слово <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>, следовательно, он так же разрешимый. Значит, разрешимые языки замкнуты относительно операции объединения
| + | |
| − | | + | |
| − | [[Категория:На проверку]]
| + | |