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