Язык Дайка

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью , добавив ссылки на дополнительные источники . Найти источники:  "Dyck language"  -  новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2015 г. )

Решетка из 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]
• Язык Дейка с двумя различными типами скобок можно распознать в классе сложности . ^[2] T C 0 {\displaystyle TC^{0}}
• Количество различных слов Дика с ровно n парами скобок и k самыми внутренними парами (то есть подстрокой ) является числом Нараяны .${\displaystyle [\ ]}$ ${\displaystyle \operatorname {N} (n,k)}$
• Количество различных слов Дика с ровно n парами скобок является n -м каталонским числом . Обратите внимание, что язык Дика слов с n парами скобок равен объединению по всем возможным k языкам Дика слов из n пар скобок с k самыми внутренними парами , как определено в предыдущем пункте. Поскольку k может принимать значения от 0 до n , мы получаем следующее равенство, которое действительно выполняется:${\displaystyle C_{n}}$

${\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},{\mathcal {D}}_{1},\ldots ,\}}$${\displaystyle {\mathcal {D}}={\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}}$

Обобщения [ править ]

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

См. Также [ править ]

• Дайк конгруэнтность
• Решетчатое слово

Заметки [ править ]

Ссылки [ править ]

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