язык Дейка

В теории формальных языков информатики представляет , математики и лингвистики слово Дейка собой сбалансированную строку скобок.Совокупность слов Дика образует язык Дика . Самый простой, D1, использует только две совпадающие скобки, например ( и ).

Слова и язык Дейка названы в честь математика Вальтера фон Дейка . Они применяются при анализе выражений, которые должны иметь правильно вложенную последовательность скобок, например арифметических или алгебраических выражений.

Формальное определение

Позволять $\Sigma =\{[,]\}$ — алфавит, состоящий из символов [ и ]. Позволять $\Sigma ^{*}$ обозначим его замыкание Клини .Язык Дейка определяется как:

\{u\in \Sigma ^{*}\vert {\text{ all prefixes of }}u{\text{ contain no more ]'s than ['s}}{\text{ and the number of ['s in }}u{\text{ equals the number of ]'s}}\}.

Контекстно-свободная грамматика

В некоторых ситуациях может быть полезно определить язык Дейка с помощью контекстно-свободной грамматики .Язык Дайка генерируется контекстно-свободной грамматикой с одним нетерминальным $S$ и постановкой:

С \to ε | " SS " [

То есть S — это либо пустая строка ( $ε$ ), либо «[», элемент языка Дика, соответствующий «]» и элемент языка Дика.

Альтернативная контекстно-свободная грамматика языка Дейка задается постановкой:

С \to («[» С »]») *

То есть S — это ноль или более вхождений комбинации «[», элемента языка Дика, и соответствующего «]», где несколько элементов языка Дика в правой части продукции могут отличаться от друг друга.

Альтернативное определение

В других контекстах вместо этого может быть полезно определить язык Дейка, разделив $\Sigma ^{*}$ на классы эквивалентности следующим образом.Для любого элемента $u\in \Sigma ^{*}$ длины $|u|$ , мы определяем частичные функции $\operatorname {insert} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}$ и $\operatorname {delete} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}$ к

\operatorname {insert} (u,j)

является

u

с "

[]

"вставлено в

j

позиция

\operatorname {delete} (u,j)

является

u

с "

[]

"удалено из

j

позиция

с пониманием того, что $\operatorname {insert} (u,j)$ не определено для $j>|u|$ и $\operatorname {delete} (u,j)$ не определено, если $j>|u|-2$ . Определим отношение эквивалентности $R$ на $\Sigma ^{*}$ следующим образом: для элементов $a,b\in \Sigma ^{*}$ у нас есть $(a,b)\in R$ тогда и только тогда, когда существует последовательность нуля или более применений $\operatorname {insert}$ и $\operatorname {delete}$ функции, начинающиеся с $a$ и заканчивая $b$ . То, что последовательность нулевых операций разрешена, рефлексивность объясняет $R$ . Симметрия следует из наблюдения, что любая конечная последовательность применений $\operatorname {insert}$ к строке можно отменить с помощью конечной последовательности применений $\operatorname {delete}$ . Транзитивность ясна из определения.

Отношение эквивалентности разделяет язык $\Sigma ^{*}$ на классы эквивалентности. Если мы возьмем $\epsilon$ для обозначения пустой строки, то язык, соответствующий классу эквивалентности $\operatorname {Cl} (\epsilon )$ называется языком Дейка .

Характеристики

Язык Дейка замкнут по отношению к операции конкатенации .
Леча $\Sigma ^{*}$ как алгебраический моноид при конкатенации, мы видим, что структура моноида переходит на фактор $\Sigma ^{*}/R$ , что приводит к синтаксическому моноиду языка Дейка . Класс $\operatorname {Cl} (\epsilon )$ будет обозначен $1$ .
Синтаксический моноид языка Дейка не коммутативен : если $u=\operatorname {Cl} ([)$ и $v=\operatorname {Cl} (])$ затем $uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu$ .
С учетом приведенных выше обозначений $uv=1$ но ни $u$ ни $v$ обратимы в $\Sigma ^{*}/R$ .
Синтаксический моноид языка Дика изоморфен бициклической полугруппе в силу свойств $\operatorname {Cl} ([)$ и $\operatorname {Cl} (])$ описано выше.
По теореме о представлении Хомского-Шютценбергера любой контекстно-свободный язык представляет собой гомоморфный образ пересечения некоторого регулярного языка с языком Дика на одном или нескольких типах пар скобок. ^[1]
Язык Дейка с двумя различными типами скобок можно распознать в классе сложности. $TC^{0}$ . ^[2]
Количество различных слов Дика ровно с $n$ парами круглых скобок и $k$ самыми внутренними парами (а именно, подстрокой $[\ ]$ ) — число Нараяны $\operatorname {N} (n,k)$ .
Количество различных слов Дика, в которых ровно $n$ пар скобок, есть $n$ -е каталонское число. $C_{n}$ . Обратите внимание, что язык Дика слов с $n$ парами круглых скобок равен объединению по всем возможным $k$ языков Дика слов с $n$ парами круглых скобок с $k$ самыми внутренними парами , как определено в предыдущем пункте. Поскольку $k$ может принимать значения от 0 до $n$ , мы получаем следующее равенство, которое действительно имеет место:

C_{n}=\sum _{k=1}^{n}\operatorname {N} (n,k)

Примеры

Мы можем определить отношение эквивалентности $L$ на языке Дейка ${\mathcal {D}}$ . Для $u,v\in {\mathcal {D}}$ у нас есть $(u,v)\in L$ тогда и только тогда, когда $|u|=|v|$ , то есть $u$ и $v$ иметь одинаковую длину. Это отношение разделяет язык Дейка: ${\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots \}$ . У нас есть ${\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D}}_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}$ где ${\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}$ . Обратите внимание, что ${\mathcal {D}}_{n}$ пусто для нечетного $n$ .

Введя слова Дика о длине $n$ , мы можем ввести на них связь. Для каждого $n\in \mathbb {N}$ мы определяем отношение $S_{n}$ на ${\mathcal {D}}_{n}$ ; для $u,v\in {\mathcal {D}}_{n}$ у нас есть $(u,v)\in S_{n}$ тогда и только тогда, когда $v$ можно добраться из $u$ серией правильных обменов . Правильный обмен одним словом $u\in {\mathcal {D}}_{n}$ заменяет вхождение '][' на '[]'.Для каждого $n\in \mathbb {N}$ отношение $S_{n}$ делает ${\mathcal {D}}_{n}$ в частично упорядоченное множество . Отношение $S_{n}$ является рефлексивным, поскольку пустая последовательность правильных перестановок занимает $u$ к $u$ . Транзитивность возникает потому, что мы можем расширить последовательность правильных перестановок, которая принимает $u$ к $v$ путем объединения его с последовательностью правильных обменов, которая занимает $v$ к $w$ образуя последовательность, которая принимает $u$ в $w$ . Чтобы увидеть это $S_{n}$ также антисимметрична, введем вспомогательную функцию $\sigma _{n}:{\mathcal {D}}_{n}\rightarrow \mathbb {N}$ определяется как сумма по всем префиксам $v$ из $u$ :

\sigma _{n}(u)=\sum _{vw=u}{\Big (}({\text{count of ['s in }}v)-({\text{count of ]'s in }}v){\Big )}

Следующая таблица иллюстрирует это $\sigma _{n}$ относительно строго монотонно правильных перестановок.

Строгая монотонность $\sigma _{n}$
частичные суммы $\sigma _{n}(u)$	$P$	$P-1$	$P$	$Q$
$u$	$\ldots$	]	[	$\ldots$
$u'$	$\ldots$	[	]	$\ldots$
частичные суммы $\sigma _{n}(u')$	$P$	$P+1$	$P$	$Q$
Разница частичных сумм	0	2	0	0

Следовательно $\sigma _{n}(u')-\sigma _{n}(u)=2>0$ так $\sigma _{n}(u)<\sigma _{n}(u')$ когда есть правильный обмен, который занимает $u$ в $u'$ . Теперь, если мы предположим, что оба $(u,v),(v,u)\in S_{n}$ и $u\neq v$ , то существуют непустые последовательности правильных перестановок такие $u$ принимается во внимание $v$ и наоборот. Но тогда $\sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)$ что бессмысленно. Поэтому всякий раз, когда оба $(u,v)$ и $(v,u)$ находятся в $S_{n}$ , у нас есть $u=v$ , следовательно $S_{n}$ является антисимметричным.

Частично упорядоченное множество $D_{8}$ показано на иллюстрации, сопровождающей введение, если мы интерпретируем [ как движение вверх, а ] как движение вниз.

Обобщения

Существуют варианты языка Дейка с несколькими разделителями, например, D2 в алфавите «(», «)», «[» и «]». Слова такого языка - это слова, которые заключены в круглые скобки для всех разделителей, т. е. можно читать слово слева направо, помещать каждый открывающий разделитель в стек, и всякий раз, когда мы достигаем закрывающего разделителя, мы должны иметь возможность чтобы вытащить соответствующий открывающий разделитель из вершины стека. (Приведенный выше алгоритм подсчета не обобщает).

См. также

Примечания

^ Камбиты, Коммуникации в алгебре, том 37, выпуск 1 (2009) 193-208.
^ Баррингтон и Корбетт, Information Processing Letters 32 (1989) 251-256

Ссылки

[1] Камбиты, Коммуникации в алгебре, том 37, выпуск 1 (2009) 193-208.

[2] Баррингтон и Корбетт, Information Processing Letters 32 (1989) 251-256

[1]

[2]