Изменения

[[Файл:Автомат и правые контексты 1.png|300px315px|thumb|right|Автомат на правых контекстах. Легенда: <font color=orchit>начальное</font> / <font color=orange>промежуточное</font> / <font color=red>дьявольское</font> / <font color=yelloworange>терминальное</font> состояния; <font color=grey>контекст</font>]]

<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>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.

# [[Файл:Автомат и правые контексты 2.png|500px|thumb|right|Автомат к языку <tex> \{ 001, 111, 100 \} </tex>]] ==== Пример 1 ====<tex> \{ 001, 111, 100 \} </tex>#: Возникающие правые контексты:#:# : <tex> a) C_L^R(\varepsilon) = \{ 001, 111, 100 \} </tex> <br><br /> #:# : <tex> b) C_L^R(0) = \{ 01 \} </tex> <br><br /> #:# : <tex> c) C_L^R(00) = \{ 1 \} </tex> <br><br /> #:# : <tex> d) C_L^R(001) = \{ \varepsilon \} </tex> <br><br /> #:# : <tex> e) C_L^R(1) = \{ 11, 00 \} </tex> <br><br />#:# : <tex> f) C_L^R(10) = \{ 0 \} </tex> <br><br /> #:# : <tex> g) C_L^R(100) = \{ \varepsilon \} </tex> <br><br /> #:# : <tex> h) C_L^R(11) = \{ 1 \} </tex> <br><br />#:# : <tex> j) C_L^R(111) = \{ \varepsilon \} </tex> <br><br />#:# : <tex> k) C_L^R(X) = \varnothing </tex>, где <tex> X </tex> {{---}} множество остальных аргументов.<br><br />#: Начальное состояние {{---}} 1 (<tex> C_L^R(\varepsilon) a</tex> рассматривалось в нём).#: Допускающие состояния: 4<tex>d, 7g, 9 j</tex> (в них <tex> \varepsilon \in C_L^R(...\ldots) </tex>).#: Состояние 10 <tex>k</tex> {{--- }} [[Детерминированные_конечные_автоматы#допускает|тупиковоедьявольское]].Всего 8 состояний (именно столько имеется различных контекстов).:[[Файл:Автомат и правые контексты 3.png|350px|thumb|right|Автомат к языку <tex> 0^*11 </tex>]]==== Пример 2 ====# <tex> 0^*11 </tex>#: Возможные правые контексты (аргументы упорядочены в лексикографическом порядке):#:# : <tex> a) C_L^R(0^*) = 0^*11 </tex> <br><br /> #:# : <tex> b) C_L^R(0^*1) = 1 </tex> <br><br /> #:# : <tex> c) C_L^R(0^*10(0|1)^*) = \varnothing </tex> <br><br /> #:# : <tex> d) C_L^R(0^*11) = \varepsilon </tex> <br><br />#:# : <tex> e) C_L^R(0^*11(0|1)^+) = \varnothing </tex> <br><br />#: Итого 4 состояния; начальное состояние 1<tex>a</tex>, допускающее 4<tex>d</tex>, состояние 3<tex>c</tex>&5 <tex>e</tex> {{---}} тупиковоедьявольское.

'''Интересный моментЛюбопытное замечание:''' <tex>C_L(\varepsilon)</tex> состоит из всех пар строк, которые при конкатенации дают слово из языка.

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

:Пусть <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^* \} | \le 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>.

Также введём на <tex>\Sigma^*</tex> Введём следующее отношение эквивалентностина строках:

<br/>Оценим количество классов, на которые отношение <tex>\cong</tex> разбивает язык <tex>L</tex>. Сопоставим состояниям автомата Для этого пронумеруем состояния, и каждому слову <tex> \mathcal{A}omega</tex> числа: сопоставим вектор <tex>a_{\forall q_i omega} \in Q, q_i \leftrightarrow num(q_i) = i^{|Q|} </tex>. Каждый класс эквивалентности можно закодировать вектором такой, что <tex>aa_{\omega}[i] = q_j \Leftrightarrow q_i \cdot \omega = q_j </tex> из . Количество различных таких векторов {{---}} <tex>{|Q|}^{|Q|} </tex> чисел, изменяющихся в диапазоне <!--- (поскольку <tex>\forall i = 1..\ldots |Q|</tex>. Положим <tex>:\ a[i] = num(q_i 1 \cdot x)ldots |Q| </tex> {{) ---}} номер состояния, в которое попадём, если начнём с состояния <tex>q_i. В то же время неэквивалентным словам соответствуют разные </tex>, и пойдём по строке <tex>xa </tex> посимвольно, где <tex>xтогда количество классов эквивалентности также ограничено </tex> {{---}} слово из кодируемого класса эквивалентности. Количество различных векторов данного вида {{---}} <tex>|Q|}^{|Q|}</tex>. Остаётся показать, а количество классов что существует взаимно-однозначное соответствие между нашими классами эквивалентности не превосходит этого значенияи синтаксическими моноидами.Смотрим:Если <br><tex>x \cong y</tex> и <br><tex>uxv \in LLeftrightarrow </tex>, то <br><tex>s \cdot (uyvuxv) = ((s \cdot u) \cdot yx) \cdot v = ((s \cdot u) \cdot xy) \cdot v = s \cdot (uxvuyv) \in T</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 LT </tex>. Аналогично из <br><tex>uyv \in LLeftrightarrow </tex> следует <br><tex>uxv \in L \Leftrightarrow uyv \in L</tex>. Значит, <br><tex>x \cong y \Rightarrow Leftrightarrow </tex><br><tex> [[x]] = [[y]]</tex>. Следовательно, размер синтаксического моноида не превосходит количества классов эквивалентности, порождаемых отношением (<tex>\congs </tex>, которое в свою очередь не превосходит <tex>|Q|^{|Q|{---}}</tex>начальное состояние).

Покажем, что <tex>f_x = f_y \quad \Leftrightarrow \quad [[x]] = [[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>.

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

Заметим, что <tex>[[0]] \varepsilon</tex> и <tex>[[1]]\ </tex> {{---}} не имеют обратных элементов в данном моноиде, так как нейтральный элемент. Включает в себя содержит только пустую строку, а её невозможно получить из непустой с помощью конкатенации. Следовательно <tex>L</tex> не является групповым языком.

====Язык из последовательных N нулей и N единиц====Язык <tex>[[L = 0]]</tex> содержит все строки, распознаваемые регулярным выражением <tex>0(0|1)^*n1^n</tex>. задан над алфавитом <tex>\forall x \in [[0]]: C_L(x) Sigma = \{\langle u0, v \rangle \mid u \in L, v \in \Sigma^* 1\}</tex>.

Балансом слова <tex>[[1]]|\omega|_b</tex> содержит все строкиназовём число, равное разности между количеством нулей и единиц, принадлежащие встречающихся в данном слове. Если слово <tex>\omega = uxv</tex> принадлежит языку<tex>L</tex>, то есть, распознаваемые регулярным выражением <tex>1|x|_b = -(0|1u|_b + |v|_b)^*</tex>. Но <tex>\forall |x \in [[1]]: C_L(|_b</tex> может принимать любое целое значение, при том, что <tex>x) = C_L(\varepsilon) \cup \{\langle \varepsilon, v \rangle \mid v \in \Sigma^* \}</tex>имеет непустой двухсторонний контекст.

ЗаметимЗначит, что синтаксический моноид <tex>[[0]]</tex> и <tex>[[1]]M(L)</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> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.Анализ свойств регулярных языков]]* [[Доказательство нерегулярности языков: лемма о разрастании]]

== Ссылки Источники информации ==

* [http://en.wikipedia.org/wiki/Syntactic_monoid Wikipedia {{---}} Syntactic monoid - Wikipedia]