язык Дик

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

В теории формальных языков информатики , математики и лингвистики слово Дика — это сбалансированная строка скобок. Набор слов Дика образует язык Дика . Самый простой, Дика-1, использует всего две парные скобки, например ( и ) .

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

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

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{ все префиксы }}u{\text{ содержат не больше ]-х символов, чем ['s}}{\text{ и количество ['s в }}u{\text{ равно количеству ]-х символов}}\}.}$

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

С → ε | "[" С "]" С

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

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

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

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

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

${\displaystyle \operatorname {вставить} (u,j)}$с " " вставленным в th позицию${\displaystyle u}$${\displaystyle []}$${\displaystyle j}$

${\displaystyle \operatorname {удалить} (u,j)}$с удаленным " " из th позиции${\displaystyle u}$${\displaystyle []}$${\displaystyle j}$

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

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

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

Например, следующее предложение является допустимым в Dyck-3:

( [ [ ] { } ] ( ) { ( ) } ) [ ]

Предложение языка Dyck можно представить как спуск и подъем по уровням вложенных скобок. При чтении предложения Dyck каждая открывающаяся скобка увеличивает глубину вложенности на 1, а каждая закрывающаяся скобка уменьшает на 1. Глубина предложения — это максимальная глубина, достигнутая в пределах предложения.

Например, мы можем аннотировать следующее предложение, указывая глубину на каждом шаге:

0 ( 1 [ 2 [ 3 ] 2 { 3 } 2 ] 1 ( 2 ) 1 { 2 ( 3 ) 2 } 1 ) 0 [ 1 ] 0

и все предложение имеет глубину 3.

Мы определяем Dyck-(k, m) как язык с k типами скобок и максимальной глубиной m. Это имеет приложения в формальной теории рекуррентных нейронных сетей . ^[1]

• Язык Dyck закрыт относительно операции конкатенации .
• Рассматривая как алгебраический моноид при конкатенации, мы видим, что структура моноида переносится на фактор , в результате чего получается синтаксический моноид языка Дика . Класс будет обозначаться .${\displaystyle \Сигма ^{*}}$ ${\displaystyle \Сигма ^{*}/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 \Сигма ^{*}/R}$
• Синтаксический моноид языка Дика изоморфен бициклической полугруппе в силу свойств и описанных выше.${\displaystyle \operatorname {Cl} ([)}$${\displaystyle \operatorname {Cl} (])}$
• По теореме Хомского–Шютценбергера о представлении любой контекстно-свободный язык является гомоморфным образом пересечения некоторого регулярного языка с языком Дика по одному или нескольким видам пар скобок. ^[2]
• Язык Дика с двумя различными типами скобок можно распознать в классе сложности . ^[3]${\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 о словах Дика