Изменения

:Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой <tex>\left( C_L^R(\varepsilon) = L \right)</tex>. Вершины, контексты которых содержат <tex>\varepsilon</tex>, должны быть допускающими. :Покажем что полученный автомат допускает в точности указанный язык. Выпишем свойства, которые мы стремились удовлетворить при построении::: 1. <tex> u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(xc) \quad \Leftrightarrow leftrightarrow \quad \langle u,c \rangle \vdash \langle v, \varepsilon \rangle </tex>:: 2. <tex> s \quad \leftrightarrow \quad C_L^R(\varepsilon) , </tex>, где <tex> s </tex> {{---}} стартовое состояние.:: 3. <tex> \varepsilon \in C_L^R(\omega) \quad \Leftrightarrow \quad v \in T \quad ( v \quad \leftrightarrow \quad C_L^R(\omega) ) </tex>:Из 1 следует:: 1*. <tex> u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(x \omega) \quad \Leftrightarrow \quad \langle u,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>:Положив <tex> s = u </tex> и учтя 2, получим:: <tex> v \quad \leftrightarrow \quad C_L^R(\omega) \quad \Leftrightarrow \quad \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>:Теперь зафиксируем за состоянием <tex> v </tex> контекст <tex> C_L^R(\omega) </tex>. Тогда левая часть 3 равносильна <tex> \omega \in L </tex>, а правая, с учётом <tex> \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>, означает, что автомат допускает <tex> \omega </tex>.

 :Пусть <tex>L</tex> {{---}} регулярный. В таком случае существует автомат <tex>\mathcal{A}</tex>, распознающий его. :Рассмотрим произвольное слово <tex>y</tex>. Положим <tex>u</tex> {{---}} такое состояние <tex>\mathcal{A}</tex>, в которое можно перейти из начального по слову <tex>y</tex>. Тогда <tex>C_L^R(y)</tex> совпадает с множеством слов, по которым из состояния <tex>u</tex> можно попасть в допускающее. :Причем если по какому-то слову <tex>z</tex> тоже можно перейти из начального состояния в <tex>u</tex>, то <tex>C_L^R(y) = C_L^R(z)</tex>. Наоборот, если <tex>C_L^R(y) = C_L^R(z)</tex>, то состояния, в которые можно перейти по словам <tex>y</tex> и <tex>z</tex>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.

==== Пример 1 ====<tex> \{ 001, 111, 100 \} </tex> ====

: Начальное состояние {{---}} <tex>a</tex> . Допускающие состояния: <tex>d, g, j</tex> (в них <tex> \varepsilon \in C_L^R(...\ldots) </tex>). Состояние <tex>k</tex> {{---}} [[Детерминированные_конечные_автоматы#допускает|дьявольское]]. Всего 8 состояний (именно столько имеется различных контекстов).

==== Пример 2 ====<tex> 0^*11 </tex> ====

<br />:Заметим, что <tex> \{ z \mid \langle \varepsilon, z \rangle \in C_L(y) \} = C_L^R(y) </tex>. Следовательно, если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.

<br />:Пусть <tex>L</tex> {{---}} регулярный. В таком случае существует детерминированный автомат <tex>\mathcal{A}</tex>, распознающий его. Понятно, что для любого слова <tex> xyz </tex>, допускаемого автоматом, существуют <tex> u ,\ v </tex> такие, что <tex> s \cdot x = u ,\ u \cdot y = v ,\ v \cdot z \in T </tex> (где <tex> s </tex> {{---}} начальное состояние). :Тогда справедливо равенство <tex> C_L(y) = \bigcup\limits_{(u, v) :\ u \cdot y = v} \{ \langle x, z \rangle \mid s \cdot x = u ,\ v \cdot z \in T \} </tex>. Учитывая <tex> | \{ (u, v) \mid u,v \in Q \} | = |Q|^2 </tex>, получаем <tex> | \{ C_L(y) \mid y \in \Sigma^* \} | \leqslant 2^{|Q|^2} </tex>, то есть множество контекстов конечно.

'''Синтаксическим моноидом''' (англ. ''syntactic monoid'') <tex>M(L)</tex> языка <tex>L</tex> называется множество, состоящее из его классов эквивалентности <tex>[[x]] = \{ y \in \Sigma^* \mid C_L(x) = C_L(y) \}\ </tex>, с введённым на нём операцией конкатенации <tex>\circ</tex>, где <tex>[[x]]\circ[[y]] = [[xy]]\ \ </tex>. Нейтральным элементом в нём является <tex>[[\varepsilon]]</tex>.

<br/>Оценим количество классов, на которые отношение <tex>\cong</tex> разбивает язык <tex>L</tex>. Для этого пронумеруем состояния, и каждому слову <tex> \omega</tex> сопоставим вектор <tex> a_{\omega} \in Q^{|Q|} </tex> такой, что <tex> a_{\omega}[i] = q_j \Leftrightarrow q_i \cdot \omega = q_j </tex>. Количество различных таких векторов {{---}} <tex> {|Q|}^{|Q|} </tex><!--- (поскольку <tex> \forall i = 1..\ldots |Q| :\ a[i] = 1..\ldots |Q| </tex>) --->. В то же время неэквивалентным словам соответствуют разные <tex> a </tex>, тогда количество классов эквивалентности также ограничено <tex> {|Q|}^{|Q|} </tex>.

<br><tex> s \cdot (uxv) = ((s \cdot u) \cdot x) \cdot v = ((s \cdot u) \cdot y) \cdot v = s \cdot (uyv) \ </tex> (пусть <tex> s \cdot u </tex> равно <tex> = q </tex> из определения <tex> \cong </tex>, тогда <tex> (s \cdot u) \cdot x = q \cdot x = q' = q \cdot y = (s \cdot u) \cdot y \ </tex>)

 :Данный факт был показан в доказательстве предыдущей леммы, он не требует минимальности автомата.

 :Пусть <tex>[[x]] = [[y]]\ </tex> и <tex>q \in Q</tex>. Тогда <tex>q = s \cdot u</tex> для некоторого слова <tex>u</tex>. Пусть <tex>q_1 = f_x(q) = s \cdot ux</tex> и <tex>q_2 = f_y(q) = s \cdot uy</tex>. Поскольку <tex>[[x]] = [[y]]</tex>, справедливо <tex>uxv \in L \quad \Leftrightarrow \quad uyv \in L</tex>. Следовательно, <tex>q_1 \cdot v \in T \Leftrightarrow q_2 \cdot v \in T</tex>, то есть <tex>q_1</tex> и <tex>q_2</tex> эквивалентны. Значит, <tex>q_1 = q_2</tex>, так как автомат <tex>\mathcal{A}</tex> минимален. То есть, <tex>f_x = f_y</tex>.

====Язык <tex>L = \{\omega \mid |\omega| \bmod 2 = 0 \}</tex>слов четной длины====

<tex>\{\langle u, v \rangle \mid uxv \in L\}</tex> {{---}} это множество всех пар <tex>\langle u,v \rangle</tex>, таких что <tex>|u| + |v| = |x|</tex> <tex>\ (\mathrm{mod</tex> <tex>} \ 2)</tex>.

====Язык <tex>L</tex> над алфавитом <tex>\Sigma = \{из 0и 1,заданный регулярным выражением 1(0|1\}</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> не является групповым языком.

====Язык <tex>L = 0^n1^n</tex> над алфавитом <tex>\Sigma = \{0,1\}</tex>из последовательных N нулей и N единиц====