Изменения

Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \sumSigma^*\}</tex> его правых контекстов конечно.

<br/>:Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой ( <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 \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>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.

Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^L(y) \mid y \in \sumSigma^*\}</tex> его левых контекстов конечно.

{{ТеоремаЛемма

Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \sumSigma^*\}</tex> его двухсторонних контекстов конечно.

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

:Пусть <tex>L</tex> {{---}} регулярный. Тогда В таком случае существует детерминированный автомат <tex>\mathcal{A}</tex>, распознающий его. Рассмотрим произвольное слово Понятно, что для любого слова <tex>yxyz </tex>. Пусть , допускаемого автоматом, существуют <tex>u ,\langle iv </tex> такие,y что <tex> s \rangle cdot x = u ,\vdash^* u \langle u_i(cdot y)= v , \varepsilon v \rangle, i = 1,2,cdot z \ldots,nin T </tex> (где <tex>n</tex> — число состояний <tex>As </tex>{{---}} начальное состояние). Если для какого-то слова :Тогда справедливо равенство <tex>z</tex> выполняется <tex>u_iC_L(y) = u_i\bigcup\limits_{(zu, v):\ u \cdot y = v} \{ \langle x, i z \rangle \mid s \cdot x = 1,2u ,\ldots,nv \cdot z \in T \} </tex>, то . Учитывая <tex>C_L| \{ (yu, v) \mid u,v \in Q \} | = C_L(z)|Q|^2 </tex>. Наоборот, если получаем <tex>| \{ C_L(y) = C_L(z)</tex>, то <tex>u_i(\mid y) \sim u_i(z), i = 1,in \Sigma^* \} | \leqslant 2^{|Q|^2,\ldots,n} </tex>. Таким образом, можно установить взаимное соответствие между двухсторонними контекстами и классами эквивалентности наборов <tex>u_i</tex>, которых конечное число, поскольку каждое число <tex>u_i</tex> принимает значения от <tex>1</tex> до <tex>n</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>C_L(y) [[x]]\circ C_L(z) [[y]] = C_L(yz)[[xy]] \ \ </tex>. Нейтральным элементом в нём является <tex>C_L([[\varepsilon)]]</tex>.

Пусть Язык <tex>ML</tex> {{---}} свободный моноид на регулярный <tex>\sum^*Leftrightarrow</tex>. Тогда <tex>M(L)</tex> {{---}} его синтаксический моноид определяющий язык <tex>L</tex>. Если<br># <tex>M</tex> определяет <tex>L</tex> тогда и только тогда, если <tex>M \subseteq M(L)</tex># Если <tex>M</tex> определяет <tex>L</tex> и если <tex>N \subseteq M</tex>, тогда <tex>N</tex> {{---}} определяет <tex>L</tex>конечен.

## Если Размер синтаксического моноида <tex>M(L)</tex> определяет языка <tex>L</tex>равен количеству его различных двухсторонних контекстов <tex>C_L</tex>. Применяя лемму, тогда по (1) доказанную ранее, получаем:Язык <tex>M \subseteq M(L)</tex>. Таким образом, если {{---}} регулярный <tex>N \subseteq MLeftrightarrow</tex>, то множество <tex>N \subseteq M{C_L(Ly)\mid y \in \Sigma^*\}</tex> и снова по (1) его двухсторонних контекстов конечно <tex>N\Leftrightarrow</tex> определяет его синтаксический моноид <tex>M(L)</tex>конечен.

Размер {{Лемма|statement=Пусть язык <tex>L</tex> распознается [[Детерминированные конечные автоматы|ДКА]] <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle</tex>. Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>|Q|^{|Q|}</tex>.|proof=Введём следующее отношение эквивалентности на строках:<br/><tex>x \cong y \Leftrightarrow \forall q \in Q: q \cdot x = q \cdot y</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> x \cong y </tex><br><tex> \Leftrightarrow </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 = q </tex> из определения <tex> \cong </tex>, тогда <tex> (s \cdot u) \cdot x = q \cdot x = q' = q \cdot y = (s \cdot u) \cdot y \ </tex>)<br><tex> \Leftrightarrow </tex><br><tex> s \cdot (uxv) \in T \Leftrightarrow s \cdot (uyv) \in T </tex><br><tex> \Leftrightarrow </tex><br><tex> uxv \in L \Leftrightarrow uyv \in L </tex><br><tex> \Leftrightarrow </tex><br><tex> [[x]] = [[y]] </tex>(<tex> s </tex> {{---}} начальное состояние).}} Пусть <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} [[Детерминированные конечные автоматы|ДКА]]. Каждое слово <tex>\omega \in \Sigma^*</tex> порождает отображение <tex>f_\omega : Q \rightarrow Q</tex>, определённое следующим образом: <tex>f_\omega(q) = q \cdot \omega</tex>.{{Определение|definition='''Моноидом переходов''' (англ. ''transition monoid'') <tex>M(\mathcal{A})</tex> называется множество отображений <tex>f_\omega</tex> с операцией композиции. <tex>f_x \cdot f_y = f_{xy}</tex>. Нейтральным элементом в данном моноиде является мерой структурной сложности языкаотображение <tex>f_\varepsilon</tex>. Заметим}} {{Теорема|statement=Пусть <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} минимальный [[Детерминированные конечные автоматы|ДКА]], задающий язык <tex>L</tex>. Тогда <tex>M(\mathcal{A})</tex> и <tex>M(L)</tex> изоморфны.|proof=Покажем, что <tex>f_x = f_y \quad \Leftrightarrow \quad [[x]] = [[y]]</tex>. <tex>\Rightarrow</tex><br/> :Данный факт был показан в доказательстве предыдущей леммы, он не требует минимальности автомата. <tex>\Leftarrow</tex><br/> :Пусть <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| \ (\mathrm{mod} \ 2 )</tex>. Значит, <tex>M(L)</tex> состоит из двух элементов: множества слов чётной длины и множества слов нечётной длины. Нейтральным элементом в данном моноиде является множество слов чётной длины.  Оба элемента являются обратными самим себе, значит <tex>M(L)</tex> является группой, следовательно <tex>L</tex> {{---}} групповой язык распознается автоматом . ====Язык над алфавитом из 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>n0(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 единиц====Язык <tex>nL = 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> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным. == См. также == * [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)|Анализ свойств регулярных языков]]* [[Доказательство нерегулярности языков: лемма о разрастании]] == Источники информации == * ''Howard Straubing'' Finite automata, formal logic, and circuit complexity, 1994. ISBN 3-7643-3719-2. {{---}} C. 53.* ''James A. Anderson'' Automata theory with modern applications, 2006. ISBN 0-521-61324-8. {{---}} С. 72.* [http://en.wikipedia.org/wiki/Syntactic_monoid Wikipedia {{---}} Syntactic monoid]