Изменения
→Примеры
=== Примеры ===
<tex>\{\langle u, v \rangle \mid uxv \in L\}</tex> {{---}} это множество всех пар <tex>\langle u,v \rangle</tex>, таких что <tex>|u| + |v| = |x|</tex> <tex>(mod</tex> <tex>2)</tex>.
Оба элемента являются обратными самим себе, значит <tex>M(L)</tex> является группой, следовательно <tex>L</tex> {{---}} групповой язык.
====Язык <tex>L</tex> над алфавитом <tex>\Sigma = \{0,1\}</tex>===='''2'''. Язык <tex>L</tex> над алфавитом <tex>\Sigma = \{0,1\}</tex> задан регулярным выражением <tex>1(0|1)^*</tex>. Его синтаксический моноид <tex>M(L)</tex> содержит три элемента:
:<tex>a)</tex> <tex>[[\varepsilon]]</tex> {{---}} нейтральный элемент. Включает в себя только пустую строку.
Заметим, что <tex>[[0]]</tex> и <tex>[[1]]</tex> не имеют обратных элементов в данном моноиде, так как нейтральный элемент содержит только пустую строку, а её невозможно получить из непустой с помощью конкатенации. Следовательно <tex>L</tex> не является групповым языком.
====Язык <tex>L = 0^n1^n</tex> над алфавитом <tex>\Sigma = \{0,1\}</tex>===='''3'''. Язык <tex>L = 0^n1^n</tex> задан над алфавитом <tex>\Sigma = \{0,1\}</tex>.
Балансом слова <tex>|\omega|_b</tex> назовём число, равное разности между количеством нулей и единиц, встречающихся в данном слове. Если слово <tex>\omega = uxv</tex> принадлежит языку <tex>L</tex>, то <tex>|x|_b = -(|u|_b + |v|_b)</tex>. Но <tex>|x|_b</tex> может принимать любое целое значение, при том, что <tex>x</tex> имеет непустой двухсторонний контекст.
