64
правки
Изменения
Нет описания правки
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> его синтаксический моноид <tex>M(L)</tex> конечен.
|proof=
Размер синтаксического моноида <tex>M(L)</tex> языка <tex>L</tex> равен количеству его различных двухсторонних контекстов <tex>C_L</tex>. Применяя лемму, доказанную ранее, получаем:Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \Sigma^*\}</tex> его двухсторонних контекстов конечно <tex>\Leftrightarrow</tex> его синтаксический моноид <tex>M(L)</tex> конечен.
}}
{{Лемма
|statement=
Пусть язык <tex>L</tex> распознается автоматом из ДКА <tex>nA = \langle \Sigma,Q,s,T,\delta \rangle</tex> состояний. Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>n|Q|^n{|Q|}</tex>.
|proof=
Введём на <tex>\Sigma^*</tex> следующие отношение эквивалентности:<br /><tex>x \equiv y \Leftrightarrow [[x]] = [[y]]</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 \equiv y</tex>. Следовательно, размер синтаксического моноида не превосходит количества классов эквивалентности, порождаемых отношением <tex>\cong</tex>, которое в свою очередь не превосходит <tex>|Q|^{|Q|}</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> {{---}} групповой язык.
== Ссылки ==
