Контексты и синтаксические моноиды

Эта статья находится в разработке!

Контексты

Правый

Определение:

Правым контекстом [math]C_L^R(y)[/math] слова [math]y[/math] в языке [math]L[/math] называется множество [math]\{z \mid yz \in L\}[/math].

Утверждение:

Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L^R(y) \mid y \in \sum^*\}[/math] его правых контекстов конечно

Левый

Определение:

Левым контекстом [math]C_L^L(y)[/math] слова [math]y[/math] в языке [math]L[/math] называется множество [math]\{z \mid zy \in L\}[/math].

Утверждение:

Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L^L(y) \mid y \in \sum^*\}[/math] его левых контекстов конечно

[math]\triangleright[/math]

Поскольку множество регулярных языков замкнуто относительно операции разворота, то из того, что [math]C_L^L(y) = \overleftarrow{C_{\overleftarrow{L}}^R(\overleftarrow{y})}[/math] и аналогичного утверждения о правых контекстах получаем требуемое.

[math]\triangleleft[/math]

Двухсторонний

Определение:

Двухсторонним контекстом [math]C_L(y)[/math] слова [math]y[/math] в языке [math]L[/math] называется множество [math]\{\langle x,z\rangle \mid xyz \in L\}[/math].

Теорема:

Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L(y) \mid y \in \sum^*\}[/math] его двухсторонних контекстов конечно

Синтаксический моноид

Определение:

Синтаксическим моноидом языка [math]L[/math] называется множество его двухсторонних контекстов с введенной на нем операцией композиции [math]\circ[/math], где [math]C_L(y) \circ C_L(z) = C_L(yz)[/math]. Нейтральным элементом в нем является [math]C_L(\varepsilon)[/math]