64
правки
Изменения
→Синтаксический моноид
|proof=
Введём на <tex>\Sigma^*</tex> следующее отношение эквивалентности:
<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>A</tex> числа. Каждый класс класПравым контекстомс эквивалентности можно закодировать вектором <tex>a</tex> из <tex>|Q|</tex> чисел, изменяющихся в диапазоне <tex>1..|Q|</tex>. Положим <tex>a[i] = num(q_i \cdot x)</tex>, где <tex>x</tex> - слово из кодируемого класса эквивалентности. Количество различных векторов данного вида {{---}} <tex>|Q|^{|Q|}</tex>, а количество классов эквивалентности не превосходит этого значения.
Если <tex>x \cong y</tex> и <tex>uxv \in L</tex>, то <tex>s \cdot (uyv) = ((s \cdot u) \cdot y) \cdot v = ((s \cdot u) \cdot x) \cdot v = s \cdot (uxv) \in T</tex>, то есть <tex>uyv \in L</tex>. Аналогично из <tex>uyv \in L</tex> следует <tex>uxv \in L</tex>. Значит, <tex>x \cong y \Rightarrow [[x]] = [[y]]</tex>. Следовательно, размер синтаксического моноида не превосходит количества классов эквивалентности, порождаемых отношением <tex>\cong</tex>, которое в свою очередь не превосходит <tex>|Q|^{|Q|}</tex>.
}}
Пусть <tex>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(A)</tex> называется множество отображений <tex>f_\omega</tex> с операцией композиции. <tex>f_x \cdot f_y = f_{xy}</tex>. Нейтральным элементом в данном моноиде является отображение <tex>f_\varepsilon</tex>.
}}
{{Теорема
|statement=
Пусть <tex>A = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} минимальный ДКА, задающий язык <tex>L</tex>. Тогда <tex>M(A)</tex> и <tex>M(L)</tex> изоморфны.
|proof=
Покажем, что <tex>f_x = f_y \Leftrightarrow [[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 \Leftrightarrow 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>A</tex> минимален. То есть, <tex>f_x = f_y</tex>.
}}
=== Примеры ===
Рассмотрим язык <tex>L = \{\omega \mid |\omega|</tex> <tex>mod</tex> <tex>2 = 0 \}</tex>. <br /><tex>\{\langle u, v \rangle \mid uxv \in L\}</tex> {{---}} это множество всех пар <tex>\langle u,v \rangle</tex>, таких что <tex>|u| + |v| = |x|</tex> <tex>(mod</tex> <tex>2)</tex>. Значит, <tex>M(L)</tex> состоит из двух элементов: множества слов чётной длины и множества слов нечётной длины. Нейтральным элементом в данном моноиде является множество слов чётной длины. Оба элемента являются обратными самим себе, значит <tex>M(L)</tex> является группой, следовательно <tex>L</tex> {{---}} групповой язык.
<br />В качестве другого примера рассмотрим язык <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> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.
== Ссылки ==
