}}
{{ТеоремаЛемма
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \Sigma^*\}</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>C_L(y) [[x]]\circ C_L(z) [[y]] = C_L(yz)[[xy]]</tex>. Нейтральным элементом в нём является <tex>C_L([[\varepsilon)]]</tex>.
}}
=== Применение ===
Синтаксический моноид <tex>M(L)</tex> определён для любого <tex>L \in \Sigma^*</tex>, однако некоторые свойства языка можно определить по структуре его синтаксического моноида. Размер синтаксического моноида является мерой структурной сложности языка.
{{Теорема
|statement=
Пусть Язык <tex>ML</tex> {{---}} свободный моноид на регулярный <tex>\Sigma^*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>конечен.
|proof=
## Если <tex>M</tex> определяет <tex>L</tex>, тогда по (1) <tex>M \subseteq M(L)</tex>. Таким образом, если <tex>N \subseteq M</tex>, то <tex>N \subseteq M(L)</tex> и снова по (1) <tex>N</tex> определяет <tex>L</tex>
}}
Размер синтаксического моноида является мерой структурной сложности языка. Заметим, что если {{Лемма|statement=Пусть язык <tex>L</tex> распознается автоматом из <tex>n</tex> состояний, . Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>n^n</tex>.|proof= }}=== Пример ===Рассмотрим язык <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>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.
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
