Контексты
Правый контекст
| Определение: |
| Правым контекстом [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]\Leftarrow[/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]C_L^R(y) = C_L^R(z)[/math], то состояния, в которые можно перейти по словам [math]y[/math] и [math]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]L[/math] — регулярный. Тогда существует автомат [math]A[/math], распознающий его. Рассмотрим произвольное слово [math]y[/math]. Пусть [math]\langle i,y \rangle \vdash^* \langle u_i(y), \varepsilon \rangle, i = 1,2,\ldots,n[/math] ([math]n[/math] - число состояний [math]A[/math]). Если для какого-то слова [math]z[/math] выполняется [math]u_i(y) = u_i(z), i = 1,2,\ldots,n[/math], то [math]C_L(y) = C_L(z)[/math]. Наоборот, если [math]C_L(y) = C_L(z)[/math], то [math]u_i(y) \sim u_i(z), i = 1,2,\ldots,n[/math]. Таким образом, можно установить взаимное соответствие между двухсторонними контекстами и классами эквивалентности наборов [math]u_i[/math], которых конечное число, поскольку каждое число [math]u_i[/math] принимает значения от [math]1[/math] до [math]n[/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] |
Размер синтаксического моноида является мерой структурной сложности языка. Заметим, что если язык распознается автоматом из [math]n[/math] состояний, размер его синтаксического моноида не превосходит [math]n^n[/math].
