390
правок
Изменения
Добавил см. также
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \Sigma^*\}</tex> его правых контекстов конечно.
|proof=
[[Файл:Автомат и правые контексты 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>]]
<tex>\Leftarrow</tex>
<tex>\Rightarrow</tex>
<br/>
:Пусть <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> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
=== Левый контекст ===
'''Двухсторонним контекстом''' (англ. ''two-sided context'') <tex>C_L(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{\langle x,z\rangle \mid xyz \in L\}</tex>.
}}
'''Интересный моментЛюбопытное замечание:''' <tex>C_L(\varepsilon)</tex> состоит из всех пар строк, которые при конкатенации дают слово из языка.
|proof=
<tex>\Leftarrow</tex>
<br /><tex>\Rightarrow</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 ,\ u \cdot y = v \} | = |Q| ^2 </tex>, получаем <tex> | \{ C_L(y) \mid y \in \Sigma^* \} | \leqslant 2^{|Q|^2} </tex>, то есть множество контекстов конечно.
}}
{{Определение
|definition=
'''Синтаксическим моноидом''' (англ. ''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>.
}}
{{Определение
'''Групповой язык''' (англ. ''group language'') {{---}} это язык, синтаксический моноид которого является [[Группа|группой]].
}}
=== Свойства ===
Синтаксический моноид <tex>M(L)</tex> определён для любого <tex>L \in \Sigma^*</tex>, однако некоторые свойства языка можно определить по структуре его синтаксического моноида. Размер синтаксического моноида является мерой структурной сложности языка.
Пусть язык <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> \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>\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>\{\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> {{---}} групповой языкнейтральный элемент. Включает в себя только пустую строку.
:<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>[[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>имеет непустой двухсторонний контекст.
== См. также ==
== Ссылки Источники информации ==
* ''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 - Wikipedia]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]