Изменения

'''1'''. Рассмотрим язык <tex>L = \{\omega \mid |\omega|</tex> <tex>mod</tex> <tex>2 = 0 \}</tex>.<br/><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>M(L)</tex> является группой, следовательно <tex>L</tex> {{---}} групповой язык.

<brtex>\{\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>M(L)</tex> является группой, следовательно <tex>L</tex>В качестве другого примера рассмотрим {{---}} групповой язык .  '''2'''. Язык <tex>L</tex> над алфавитом <tex>\Sigma = \{0,1\}</tex> задан регулярным выражением <tex>1(0|1)^*</tex>. Его синтаксический моноид <tex>M(L)</tex> содержит три элемента: <tex>[[\varepsilon]]</tex> {{---}} нейтральный элемент. Включает в себя только пустую строку. <tex>C_L(\varepsilon)</tex> состоит из всех пар строк, которые при конкатенации дают слово из языка. <tex>[[1(0|1)^*]]</tex>. <tex>C_L(x) = C_L(\varepsilon) \cup \{\langle \varepsilon, v \rangle \mid v</tex> {{---}} любое <tex>\}</tex>, где <tex>x</tex> {{---}} слово из данного класса эквивалентности. <tex>[[0(0|1)^*]]</tex>. <tex>C_L(x) = \{\langle u, v \rangle \mid u \in L \}</tex>, где x {{---}} слово из данного класса эквивалентности. Заметим, что <tex>[[0(0|1)^*]]</tex> и <tex>[[1(0|1)^*]]</tex> не имеют обратных элементов в данном моноиде, так как нейтральный элемент содержит только пустую строку, а её невозможно получить из непустой с помощью конкатенации. Следовательно <tex>L</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> имеет непустой двухсторонний контекст. Значит, синтаксический моноид <tex>M(L)</tex> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.