Изменения
Нет описания правки
Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} [[Разрешимые_(рекурсивные)_языки|разрешимы]], тогда следующие языки разрешимы:
* <tex>L_1 \cup L_2</tex> {{---}} объединение <tex>L_1</tex> и <tex>L_2</tex>;* <tex>L_1 \cap L_2</tex> {{---}} пересечение <tex>L_1</tex> и <tex>L_2\</tex>;* <tex>\overline{L_1}</tex> {{---}} дополнение <tex>L_1\</tex>;* <tex>L_1 \backslash L_2</tex> {{---}} разность <tex>L_1</tex> и <tex>L_2</tex>;* <tex>L_1 \times L_2</tex> {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2</tex>;* <tex>L_1^*</tex> {{---}} замыкание Клини <tex>L_1</tex>;
* <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2</tex>.
Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} [[Перечислимые_языки|перечислимы]], тогда следующие языки перечислимы:
* <tex>L_1 \cup L_2</tex> {{---}} объединение <tex>L_1</tex> и <tex>L_2</tex>;* <tex>L_1 \cap L_2</tex> {{---}} пересечение <tex>L_1</tex> и <tex>L_2\</tex>;* <tex>L_1 \times L_2</tex> {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2</tex>;* <tex>L_1^*</tex> {{---}} замыкание Клини <tex>L_1</tex>;
* <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2</tex>.
Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть неперечислимы:
* <tex>\overline{L_1}</tex> {{---}} дополнение <tex>L_1\</tex>;
* <tex>L_1 \backslash L_2</tex> {{---}} разность <tex>L_1</tex> и <tex>L_2</tex>.
}}
== Литература Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]
