Контексты и синтаксические моноиды — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 30: Строка 30:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Синтаксическим моноидом''' языка <tex>L</tex> называется множество его двухсторонних контекстов с введенной на нем операцией композиции <tex>\circ</tex>
+
'''Синтаксическим моноидом''' языка <tex>L</tex> называется множество его двухсторонних контекстов с введенной на нем операцией композиции <tex>\circ</tex>, где <tex>C_L(y) \circ C_L(z) = C_L(yz)</tex>. Нейтральным элементом в нем является <tex>C_L(\varepsilon)</tex>
 
}}
 
}}

Версия 21:40, 25 сентября 2010

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


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


Определение:
Левым контекстом [math]C_L^L(y)[/math] слова [math]y[/math] в языке [math]L[/math] называется множество [math]\{z \mid zy \in L\}[/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^R(y) \mid y \in \sum^*\}[/math] его правых контекстов конечно
Утверждение:
Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L^L(y) \mid y \in \sum^*\}[/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]