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

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

Контексты

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

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

Правым контекстом (англ. 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][[x]] = \{ y \in \Sigma^* \mid C_L(x) = C_L(y) \}[/math], с введённым на нём операцией конкатенации [math]\circ[/math], где [math][[x]]\circ[[y]] = [[xy]][/math]. Нейтральным элементом в нём является [math][[\varepsilon]][/math].

Применение

Синтаксический моноид [math]M(L)[/math] определён для любого [math]L \in \Sigma^*[/math], однако некоторые свойства языка можно определить по структуре его синтаксического моноида. Размер синтаксического моноида является мерой структурной сложности языка.

Теорема:

Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] его синтаксический моноид [math]M(L)[/math] конечен.

Лемма:

Пусть язык [math]L[/math] распознается автоматом из [math]n[/math] состояний. Тогда размер его синтаксического моноида [math]M(L)[/math] не превосходит [math]n^n[/math].

Пример

Рассмотрим язык [math]L = \{\omega \mid |\omega|[/math] [math]mod[/math] [math]2 = 0 \}[/math].
[math]\{\langle u, v \rangle \mid uxv \in L\}[/math] — это множество всех пар [math]\langle u,v \rangle[/math], таких что [math]|u| + |v| = |x|[/math]. Значит, [math]M(L)[/math] состоит из двух элементов: множества слов чётной длины и множества слов нечётной длины. Нейтральным элементом в данном моноиде является множество слов чётной длины.

Литература

• Howard Straubing Finite automata, formal logic, and circuit complexity, 1994. ISBN 3-7643-3719-2. — C. 53.
• James A. Anderson Automata theory with modern applications, 2006. ISBN 0-521-61324-8. — С. 72.