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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 12: Строка 12:
 
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \sum^*\}</tex> его правых контекстов конечно
 
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \sum^*\}</tex> его правых контекстов конечно
 
|proof=
 
|proof=
 +
<tex>\Rightarrow</tex>:
 +
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>A</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>u</tex> {{---}} состояние <tex>A</tex>, в которое можно перейти из начального по слову <tex>y</tex>. Тогда <tex>C_L^R(y)</tex> совпадает с множеством слов, по которых из состояния <tex>u</tex> можно попасть в допускающее. Причем если по какому-то слову <tex>z</tex> тоже можно перейти из начального состояния в <tex>u</tex>, то <tex>C_L^R(y) = C_L^R(z)</tex>.
 
}}
 
}}
  
Строка 37: Строка 39:
 
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \sum^*\}</tex> его двухсторонних контекстов конечно
 
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \sum^*\}</tex> его двухсторонних контекстов конечно
 
|proof=
 
|proof=
 +
<tex>\Leftarrow</tex>:
 +
Если множество двухсторонних контекстов языка конечно, то, очевидно, конечно и множество его правых контекстов, а это значит, что язык регулярный.
 +
<tex>\Rightarrow</tex>:
 
}}
 
}}
  

Версия 02:43, 26 сентября 2010

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

Контексты

Правый

Определение:
Правым контекстом [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]\triangleright[/math]

[math]\Rightarrow[/math]:

Пусть [math]L[/math] — регулярный. Тогда существует автомат [math]A[/math], распознающий его. Рассмотрим произвольное слово [math]y[/math]. Пусть [math]u[/math] — состояние [math]A[/math], в которое можно перейти из начального по слову [math]y[/math]. Тогда [math]C_L^R(y)[/math] совпадает с множеством слов, по которых из состояния [math]u[/math] можно попасть в допускающее. Причем если по какому-то слову [math]z[/math] тоже можно перейти из начального состояния в [math]u[/math], то [math]C_L^R(y) = C_L^R(z)[/math].
[math]\triangleleft[/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]\triangleright[/math]

[math]\Leftarrow[/math]: Если множество двухсторонних контекстов языка конечно, то, очевидно, конечно и множество его правых контекстов, а это значит, что язык регулярный.

[math]\Rightarrow[/math]:
[math]\triangleleft[/math]

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

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