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> L_1 </tex>. Если хотя бы в одном разбиении все подстроки будут принадлежать <tex> L_1 </tex>, то всё слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.
* Для языка <tex> L_1 L_2 : </tex>
<tex>p(x):</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_2(x_2) == 1)</tex>
'''return''' <tex>1</tex> '''return''' <tex>0 </tex>
Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </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 1''' <tex>1</tex>
* Для языка <tex> L_1 \cap L_2</tex>:
<tex>p(x):</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1''' <tex>1</tex>
* Для языка <tex> L_1 \times L_2</tex>:
<tex>p(\langle x, y \rangle):</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1''' <tex>1</tex>
* Для языка <tex> L_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 1'''<tex>1</tex>
* Для языка <tex> L_1 L_2 </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>
'''return 1'''<tex>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> не всегда перечислим.
}}
== См. также ==
* [[Разрешимые (рекурсивные) языки]]
* [[Перечислимые языки]]
== Источники информации ==
