64
правки
Изменения
м
\sum -> \Sigma
{{Лемма
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \sumSigma^*\}</tex> его правых контекстов конечно.
|proof=
<tex>\Leftarrow</tex>
{{Лемма
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^L(y) \mid y \in \sumSigma^*\}</tex> его левых контекстов конечно.
|proof=
Поскольку множество регулярных языков замкнуто относительно операции разворота, то из того, что <tex>C_L^L(y) = \overleftarrow{C_{\overleftarrow{L}}^R(\overleftarrow{y})}</tex> и аналогичного утверждения о правых контекстах получаем требуемое.
{{Теорема
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \sumSigma^*\}</tex> его двухсторонних контекстов конечно.
|proof=
<tex>\Leftarrow</tex>
{{Теорема
|statement=
Пусть <tex>M</tex> {{---}} свободный моноид на <tex>\sumSigma^*</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>
