277
правок
Изменения
→Синтаксический моноид
{{Определение
|definition=
'''Синтаксическим моноидом''' <tex>M(L)</tex> языка <tex>L</tex> называется множество его двухсторонних контекстов с введенной на нем операцией конкатенации <tex>\circ</tex>, где <tex>C_L(y) \circ C_L(z) = C_L(yz)</tex>. Нейтральным элементом в нём является <tex>C_L(\varepsilon)</tex>.
}}
{{Теорема
|statement=
Пусть <tex>M</tex> {{---}} свободный моноид на <tex>\sum^*</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>
}}
Размер синтаксического моноида является мерой структурной сложности языка. Заметим, что если язык распознается автоматом из <tex>n</tex> состояний, размер его синтаксического моноида не превосходит <tex>n^n</tex>.
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
