Язык Дайка - Dyck language

Решетка из 14 слов Дика длины 8 - [ и ] интерпретируется как вверх и вниз

В теории формальные языки из Информатика, математика, и лингвистика, а Дайк слово сбалансированный нить квадратных скобок [и]. Набор слов Дика образует Язык Дайка.

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

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

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

${\displaystyle \{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, и производство:

S → ε | "[" S "]" S

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

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

S → ("[" S "]")^*

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

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

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

${\displaystyle \operatorname {insert} (u,j)}$ является ${\displaystyle u}$ с "${\displaystyle []}$"вставлен в ${\displaystyle j}$-я позиция

${\displaystyle \operatorname {delete} (u,j)}$ является ${\displaystyle u}$ с "${\displaystyle []}$"удалено из ${\displaystyle j}$-я позиция

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

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

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

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

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

Примеры

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

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

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

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

Строгая монотонность ${\displaystyle \sigma _{n}}$

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

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

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

Обобщения

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

Смотрите также

• Конгруэнтность Дика
• Слово решетки

Примечания

1. Камбитес, Сообщения в алгебре Том 37 Выпуск 1 (2009) 193-208
2. Баррингтон и Корбетт, Письма об обработке информации 32 (1989) 251-256

Рекомендации

• Язык Дайка в PlanetMath.
• Доказательство теоремы Хомского-Шютценбергера
• Запись в блоге AMS о словах Дайка