64
правки
Изменения
Нет описания правки
== Синтаксический моноид ==
=== Определение Определения ===
{{Определение
|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>.
}}
{{Определение
|definition=
'''Групповой язык''' (англ. ''group language'') {{---}} это язык, синтаксический моноид которого является [[Группа|группой]].
}}
=== Применение ===
}}
=== Пример Примеры ===
Рассмотрим язык <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> {{---}} групповой язык.
== Литература Ссылки ==
* ''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 Syntactic monoid - Wikipedia]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
