1632
правки
Изменения
м
rollbackEdits.php mass rollback
* <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>p(x):</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ldots \ \land (p_1(x_n) == 1)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ldots \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return''' <tex>1</tex>
<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ldots \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ ... \dots \ \land (p_1|_k(x_n) == 1)</tex>
'''return''' <tex>1</tex>
<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ldots \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_2|_k(x_2) == 1)</tex>
Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмём язык, состоящий из всех слов. Тогда получится, что <tex> L_1 \backslash L_2 </tex> {{---}} это <tex> \overline{L_2} </tex>. Про <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, поэтому и <tex> L_1 \backslash L_2 </tex> не всегда перечислим.
}}
== См. также ==
* [[Разрешимые (рекурсивные) языки]]
* [[Перечислимые языки]]
== Источники информации ==
