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

Контексты

Правый контекст

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

Правым контекстом [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].