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

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

Контексты

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

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

Правым контекстом (англ. right context) [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 \Sigma^*\}[/math] его правых контекстов конечно.

Доказательство:

[math]\triangleright[/math]

[math]\Leftarrow[/math] Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой ([math]C_L^R(\varepsilon) = L[/math]). Вершины, контексты которых содержат [math]\varepsilon[/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]

Левый контекст

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

Левым контекстом (англ. left context) [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 \Sigma^*\}[/math] его левых контекстов конечно.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

Двухсторонним контекстом (англ. two-sided context) [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 \Sigma^*\}[/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]

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

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

Синтаксическим моноидом (англ. syntactic monoid) [math]M(L)[/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]M[/math] — свободный моноид на [math]\Sigma^*[/math]. Тогда [math]M(L)[/math] — синтаксический моноид определяющий язык [math]L[/math]. Если [math]M[/math] определяет [math]L[/math] тогда и только тогда, если [math]M \subseteq M(L)[/math] Если [math]M[/math] определяет [math]L[/math] и если [math]N \subseteq M[/math], тогда [math]N[/math] — определяет [math]L[/math]

Доказательство:

[math]\triangleright[/math]

Если [math]M[/math] определяет [math]L[/math], тогда по (1) [math]M \subseteq M(L)[/math]. Таким образом, если [math]N \subseteq M[/math], то [math]N \subseteq M(L)[/math] и снова по (1) [math]N[/math] определяет [math]L[/math]

[math]\triangleleft[/math]

Размер синтаксического моноида является мерой структурной сложности языка. Заметим, что если язык распознается автоматом из [math]n[/math] состояний, размер его синтаксического моноида не превосходит [math]n^n[/math].